users get random names across the site

[Dave]

Are you talking about people showing as logged in under random users? There's only 2 possible ways this can happen:

1. Varnish cache (or other caching software) is in fact still in use. Did your host confirm to you that it's disabled properly? Check the HTTP response headers to find out if it's actually disabled.
2. A plugin installed that's doing this. I've never heard of such issue being caused by a plugin though.

It's definitely not something caused by a default vBulletin installation.