Adrian, there are several "opinions" on the differences between enterprise and federated searches. In a previous position my team used enterprise search more effectively and although we invested heavily in a Federated search solution, it became increasingly difficult to de-dupe and merge the discoveries. In fact we had to spend a significant amount of time and resources on storage and servers (for caching speed). Unless I am mis-reading your requirements, I recommend enterprise search.
Of the Enterprise search solutions, below is Gartner's 2010 magic quadrant review of solutions. If you haven't used Gartner's magic quadrants, here is a good description of how they work. For the record we tried EMC's Email eXtender (for large repositories of PSTs) with Google and, interwoven (now Autonomy). We also tried Vivisimo.
For the record. I personally liked the Interwoven solution, but it was costly. Google had the best support.