My host - CredibleHost - allows vB3, and I don't see any reason for a host to not allow vBulletin but
reccomend phpBB! That's quite weird...
My host uses vB3 on their support forums, and it runs pretty well. My forum, although it isn't active yet, runs great, and the server load doesn't even go past 2.00, but it probably will when the site gets active (site runs on Dual 2.0GHz Xeon with HT, and 2 gigs of RAM, and hosts 132 other sites).
A host that disallows vBulletin is not in their right mind and you (thread starter) should move immediately to a reputable host.