Would it not be easier to get a domain+shared hosting with for example, 10 different hosts, and use them, instead of 1 VPS on the same host?
I was thinking the same and maybe its a bit expensive but it seems to be worth it, since IPs would be different the only thing is I am not sure if they will be C Class IP's, what you think? And name servers will be definitely different

!!
No they can't. That's another Internet myth. I've posted about this in the past and I'm not going to go and find my post about it again. Suffice to say that G would need a court order to access the domain records. They can not see who registered a private domain.
To the op - if you want to be really safe -
Register 5 domains through 5 different registrars using 5 different email address (yahoo, hotmail, gmail, etc)
Get 5 hosting accounts with 5 different webhosts
Build 5 sites using different platforms - WordPress, html, Joomla etc
NO WBT
Seriously, there's no footprint there
I was thinking exactly the same since it seems to be point of making your domain private so, people don't access to your information, not even Google since its against privacy laws.
About your recomendations I am getting 5 different hosting accounts from different companies but, I got 2 issues that are the following:
1) At least 4 websites will be in Wordpress and the other one on Media Wiki and the 4 using Wordpress will use same theme but, to fix that I can change name details on WP of theme folder and also on theme files, is that good?
2) I bought all domains with same registrant (dumb of me) and same Company (Godaddy), to fix that I was thinking to transfer my domain to other companies registrant and use different emails on each account, is that good? What other domains companies you recommend to do this?
Thanks Great info, I am trying not to leave any foot print.
to be 100% safe he will also need
to pay for this from 5 different CCs
and need to buy 5 different laptops (each with another OS)
5 new IPS and finaly he must work on each site in different time and day and work alone to be sure nobody will report him
Wow dude, you are as paranoid as me LOL
Make payment from 5 different credit cards isn't that a bit too much? Also that is private information that Google cannot get is like private domains info, this is even works is credit cards information, can someone please confirm if I am right?
About the 5 different laptos with different OS what I can do is connect from different VMWarez Virtual Computers with different Linux distributions on it, but isn't that too much? What do people with 1000 websites on network do? 1000 computeres with different OS, not enough OS LOL?
About the 5 Ips I can do on proxy?? About the time, that has to go natural but, I agree to give a margin between working on diferent websites.
I am wondering if you are been sarcastic or not

LOL
Thanks