Had a complex PDF to convert to something editable like .doc, so I had another look at what was available.
This comparative test from 2008 was very helpful, as were some readers' comments. It concluded by recommending the koolwire.com service, which was indeed quite good, and also very convenient because it can be used through email. It produced an RTF with mostly actual tables. Visually, however, the tables in this particular case would have needed quite some re-formatting to look like the original ones.
Several readers suggested the PDF-to-Word service at pdftoword.com. For me, this gave me the best looking results. It converted the complex tables into columnized sections instead, but that was fine. (As an aside, it is not very clear which engine this service is using. It is related to Nitro PDF, a commercial Windows application which is promoted from the pdtftoword.com page. Also, the Nitro PDF pages link to the free pdftoword.com service as their free version. However, the produced Word document mentions Solid Converter PDF, another commercial Windows application, in it's properties. Weird...)
I also tried the convertpdftoword.net service which others suggested. It also gave a good looking Word document, but built it with tons of independent text boxes which was quite unconvenient in my case. A closer look, showed that this service was actually using VeryPDF's PDF2Word, which produced an RTF file (but with a .doc extension). PDF2Word turns out to actually be a re-packaging of xpdf, and is free (GPL) software. The source is available, but VeryPDF sells the Windows executable.
The funny thing from theses tests: the only completely useless conversions happened to be the one from Adobe itself.
Conclusion: I had the best results with pdftoword.com. But it all depends on your source document and what you want to do with it.