Tal Freibergs when you say "due diligence", are you referring strictly to title-related issues (clear chain of title, clouds on title, no liens or mortgages, etc), or are you referring to ALL of the possible issues that could affect a landowner (like this stuff)?
If it's the former, I'm not surprised a title abstractor would just shrug off a huge error like this. If you don't have a title insurance policy, then you really have no hammers to use against them.
I do understand your frustration. I've also paid for title searches from legit title companies that have screwed up this kind of stuff (and they also didn't seem to care when I confronted them with it). It's maddening, and it makes you realize how valuable good, reliable help is when you can finally find it!
I try to avoid the sub-$5k properties these days, and this is part of the reason why... even though there's some money to be made, the BS-to-money ratio just isn't that favorable. If you're just getting started on a shoestring budget, these are great to cut your teeth on, but there are some compelling reasons to move on to bigger fish ASAP if you can.
When I was handling my own title searches, I would order the full abstract of title and go line-by-line through every recorded document associated with the property for the past 40 years. It's a very left-brain activity, and not for everyone - but it's also a great skill to have if you want to save yourself a ton of money on title work. Keep in mind, if you're just getting the abstract of title (the pile of deeds and related documents) and not asking anyone else to analyze anything for you, it's not that expensive, because you're just getting copies of documents and doing the real work yourself.
If you don't know where to find an abstractor (if you've already Googled "XYZ County Title Abstractor" and nothing comes up), you can try calling the county recorder and ask them if they know of any good ones. I've found they usually have some connections they can point me to, and they cost a lot less than going through a title company.