Well I don't know... you can get some ridiculous hardware these days (128 cores and stuff) so virtualising very large Moodle sites becomes a viable option. You have to know your stuff though. Low rent VMs with performance issues will be bad news.
In this case I would try to run the sessions on an external cache server (e.g. memcached, Redis). See (well into) section 6 in config-dist.php. You won't need anything terribly fancy to run this server. See what happens...