Giving fake info is really the worst thing that you can do, if you cannot trust a host then maybe you should not be using that host.
Hosts ask for real info mostly for security. If something were to happen to your account, and you give fake info -- how can you prove it is really your account? You screw yourself over because they can just close your account.
Another thing is that, noone is untouchable -- so stop thinking you wont get caught, if a government agency really wants to find you..... THEY WILL.
Hosts usually also have a privacy statement stating that they WILL give your information to the authorities with a warrant. No host will be willing to go to court for you for only a couple hundred dollars a month. (Probably different if you pay thousands and are a good customer, but mostlikey not since legal fees can be expensive and mostlikely they'll lose the case).
So unless you're hosting **********, or email spam, the likely hood of you actually getting into trouble or the feds looking for you are very, very slim.
So chillax
Ps.... there's no such thing as "bulletproof" & with the right persuasion those hosts will take you down in a heart beat.
Also with domains, every registrar still has to be icann accredited, so your domain can be taken down at anytime by the feds, so like hosting, nowhere is "safe", there are just places where you can receive more time, hideout for a bit, etc. Again if they want you down, you will go down, no questions asked. (That's why they're trying to come up with. P2p domain)