I'm sorry, that's not right. Trust me, my wife works with these issues all day long - they have an entire department devoted to these kinds of problems.
All a notary does is ensure that the people signing the document are who they say they are. They are backing the signatures - not the contents of the document. In fact, they don't usually even know what the document says, nor do they care.
Houses get sold with entanglements all the time. Liens and other encumbrances on the property, some that were filed with the county and some which were not but show up later. If a lender or lienholder pops up with a legitimate claim to the property, they will settle it with the property - the current owner is boned. That's why title insurance exists.
A title search is supposed to be done when a house is sold - law in most places. However, encumbrances do not always show up, some pop up years later, or even when the house is sold many years later. Title insurance is supposed to back the homeowner to protect them from exactly this kind of situation, and that's why people buy it.
In this case, it appears the title insurance company is refusing to pay - and that's the problem.