@Cleo: Besides this issue and some other weirdness with RingLead (e.g.,. if we dual post from a web form to both Marketo and SFDC - we have our reasons, but will eventually change to flow only through Marketo - then RingLead is seeing the existing record in SFDC, but proceeding to let Marketo create another one), RingLead does seem to work as advertised.
I'm a little annoyed with them that I haven't gotten an explanation of what happened, or assurance that it won't happen again.
That's one thing that bugs me about both Marketo and RingLead: There's all this stuff that happens out of sight via APIs in a black hole, and we don't have access to any kind of audit trail to monitor what's happening. It's easier to access audit trails in SFDC.
As for similar tools, we've used DemandTools with SFDC for years, and love it. We have a number of automated dedupe scripts running against our SFDC data to help keep it clean. They (CRMFusion) offer some other dupe cleaning tools, too.