I've worked for a company that was acquired by EIG. Their whole support system is incredibly terrible, but account fraud is a legitimate constant concern. The fact that the guy prepaid doesn't really matter—Paypal accounts in particular are a breeding ground for stolen money/accounts. My reading of this situation is that the person who wrote the article did something that got their account flagged as "this looks like…
What do you think is the threshold to charge to avoid the scammer harassment? I tend to use cheap hosting for people, and I'd like to step up a notch to avoid just this sort of silliness.
That said, look for services with a minimum term of a year (this lowers spammer numbers quite a bit), and look for services that have multiple contact methods including an actual physical mailing address listed on their site (even if it's just a PO Box, it shows that they're probably not a reseller... there are lot of resellers out there).
And avoid companies owned by EIG or GoDaddy (some web searching will get you lists for both)—they're both just too big and too disorganized to provide adequate levels of support.