We have migrated to a new VPS with a new host. Since then, we've been seeing problems with URL rewrites.
It's a subdirectory installation, so child sites look like:
http://domain.com/name/
The first sign of problems was that a URL could not be rewritten without the trailing slash. http://domain.com/name would take you to the 404 page on the parent site (but the menu would match up with the menu on the child site; we use WooThemes custom menus). Typing www (as http://www.domain/name) managed to rewrite the trailing slash just fine.
We opened a ticket with host support. I don't know if support actually did anything, or if it was already working for them when they got around to the ticket, but in time, more and more sites began working w/o the trailing slash. It's still inconsistent, though.
Many sites seem to be working now without the trailing slash, but not all, and I'm also seeing other inconsistent URL rewrites. For example, I typed http://domain.com/name and ended up at http://domain.com/other-name/name/. Another staffer followed a link from the parent site at http://domain.com/page/ to a child at http://domain.com/childname, which was correctly rewritten with the trailing slash, but when she hit the back button, she ended up at http://domain.com/childname/page/.
Permalinks themselves seem mostly okay. http://domain.com/page makes it to the intended destination, but http://www.domain.com/page gets routed to http://domain.com.
Let me show you the rewrite rules. Other than some custom rules so that timthumb can access cached images instead of dynamically generating everything every time, the rules are standard WP multisite rules:
<iframe src="http://pastebin.com/embed_iframe.php?i=zQaBE2DA" style="border:none;width:100%"></iframe>
I've not found anything to be consistently reproducible, but here's an example of a link that, at first, would not work without the trailing slash, and later, started directing me to an unrelated site.
http://realtronhomes.com/gordana-valois
(For example, one time it directed me to http://realtronhomes.com/stephen-greenberg/gordana-valois/.)
We disabled our caching plugin (W3 Total Cache) after the migration because of some problems, and also b/c we thought it might help this issue, so the site has been slow.
Any ideas would be appreciated. I don't know much about the server config, but could find out. It's a cloud VPS with VPS.net. Someone mentioned LightSpeed. Sorry so vague. The guy to ask is in another time zone and still sleeping. :) I'll get the details.