Out of 4 cheap VPS hosts I've used
not one has been without billing issues. Sometimes even in my favour! At least I configure them securely enough that one hosting company's admins had trouble getting in to test things when I reported the clock being wrong enough to cause problems (the host box's fault, and seriously who doesn't use NTP).