Hi,
That is NOT good news, and certainly points to the reformat and reinstall routeI've also noted, that safe mode just hangs for me, it's not working.
You might have one last shot with EWIDO:
http://www.ewido.net/en/
There is a 14 day trial of the whole thing, but you can update and use the on demand scanner after that.