I took a demo with Full Circle a couple of months back. It is awesome, and solves for this problem as well as many others. However, the price point is high, and I've been able to hack together enough of my own system with Marketo and Salesforce to get me close enough. It is too bad Marketo can't go deep enough to cheat this process, like it can in many other ways. But if someone was looking to solve it without re-inventing the wheel or banging their head on a desk for too long, Full Circle is the way to go.
Hi Harrison Yeager,
One of the things you could do here is to prevent sales from creating opportunities from nowhere in SFDC :
It will not solve everything, but at least, you will stop having opportunities without contacts.