How to configure Multisite Network with randomized hostnames?

After banging my head on this for a few days, I found a solution that works.

Just add the following to wp-config.php:

if ( isset( $_SERVER['HTTP_X_FORWARDED_HOST'] ) ) {
    $_SERVER['HTTP_HOST'] = $_SERVER['HTTP_X_FORWARDED_HOST'];
}

This will force WordPress to use the requested domain, instead of the proxy domain.