Chepos, there were some rumours of DL/AF to CDG, but nothing has surfaced. FLL is actively pursuing European service beyond Condor and Finnair Holidays. Best bet would be Air France or Delta to CDG, since there is strong O&D and a large part of the French population is now living in the FLL area. Another possibility is Icelandair to KEF. They secured the rights to FLL-KEF in 1999. Not sure if they ever flew it, but it's a possibility, especially with fleet renewal coming up (I believe they are expanding thier 757 fleet).
BA/VS/LH, etc. would be nice, but if anything they would add more flights to MIA instead of bothering with FLL. Word is (and I got this from a Miami AA employee) that AA has some pretty nice plans for FLL for the upcoming year and CCS is just the beginning. We'll see how valid those statements are next April, but I don't see how AA could not do very well flying FLL-LHR (FLL is an LHR city). Finding the slots is the hard part. None the less, on the "likely" side, I think AF/DL to CDG and Icelandair to KEF are good bets. Everything else is up in the air, but London service is bound to happen within five years.
Whatever trans-Atlantics are opened out of FLL, heavy O&D is a must for daily service (KEF is the exception, since Icelandair makes money offering cheap fares to Europe via KEF), especially since it has to compliment MIA. LON, MAD, CDG, and AMS (the four biggest Miami-Europe O&D markets, in that order) all have room for extra flights. FRA (#5 market) is good, but the traffic is too heavily concentrated heading East. MXP (#6) is a growing market from MIA because of the fashion industry ties (and FLL had Lauda Italia in the past), but it will be a while before FLL service is warranted. BCN (#7) is highly needed, but not even MIA has BCN yet. The rest will never happen (if memory serves me right, ZRH #8, MUC #9, TLV #10, BRU #11, FCO #12, DUS #13, MAN #14, CPH #15; VIE, HEL, WAW, IST, and BHX round it off).