I can say that sites such as MyLife, and Intellius are all frauds. I've tried them all. They pretty much charge you to see information commonly presented in the yellowpages. I'm surprised some lawyer hasn't class actioned these sites. If you don't believe me, find a friend with a DUI or similar on their record and see what comes up.
The problem is that most states have archaic and expensive methods for pulling criminal and background records. If you want proof, just google "LA County Criminal Records". Some counties provide this information for free, but they are few and far between.
I'm looking for something similar. I run a site called https://rentersfriend.com. We provide credit and background checks on apartment listings. I've switched around our background data provider 6 times in the last year and still haven't found one that completely satisfies what I need. Unfortunately the nature of the beast is that high quality checks are slow and expensive.