Aargh, sometimes bureaucracy drives me nuts!
There are changes to the statutes regulating bonds and motor vehicle sales that will become effective 8/1/2012. (MN Statute 168A.07 [Laws 2012, Chapter 287]). Right now DVS is creating the forms and policies to enact these changes, so I can share more in a few weeks.
Basically, if there is an ownership record on file but you dont have that title, you can obtain a surety bond to protect against that claim of ownership. Also required will be an affidavit and attestation statement indicating rightful ownership and that due diligence was made in attempting to contact the prior owner to obtain title.
So, wait 3 weeks and then go into a local office.