So, this is kind of a sideways suggestion, but... we just moved Wikitravel to a Web hosting service (xlinternet.com). It's working pretty much great, right out of the box.
Considering that MediaWiki runs on some pretty standard software (PHP, mySQL), I wonder if it wouldn't be a good idea to leave most of the yucky sysadmining problems up to folks who make it their business. I'm sure that a project as big as Wikimedia could get some special treatment.
I don't know what kind of bandwidth and storage requirements Wikimedia has, but I doubt that they'd be insurmountable with any given Web hosting service.
Just a suggestion to consider.
~ESP