I saw raven tools at pubcon, which I think uses majestic on the backend?. They had a 'recent links' tool that didn't work - didn't show some pretty serious links I'd developed in the last couple of weeks. Still, lots of people seem to talk about them.
Hi Planet13, we discussed this in another thread. I am not so sure if the paid tools offer so much value and I agree with Weel about their index not being updated frequently enough so you see a lot of links which do not exist or the webmaster has updated the page with all link opportunities lost. I find this in both OSE and RavenTools.
Personally I like using Raven Tools for its UI and its features other than link building. Link-building-wise it does include data from Majestic, including what it calls the "historical" and the "fresh" index.
Recently I tried some free tools which definitely don't provide as much data but they offer good opportunities for finding links.
Backlinkwatch is a nice free tool as well as the Backlink Builder of Webconfs.
But I think the best tool of them all (paid and free) is a Google search with advanced operators. You can find gems if you search right.