Including applying the patch and changing the internal.xml.
I've deleted all default Web Cache data (origin servers/sites and mappings) and added the two AS's as origin servers, created a site (designated 'default') with the same hostname as the Web Cache machine and created a mapping between that site and the two originating servers.
If I use the url of the Web Cache machine, I get the default Web Cache welcome screen (where I expected to see the AS welcome screen of one of the origin servers), but if I add /em to that url, I indeed get the AS login screen, but as soon as I login, i get reditected the AS machine (the url is no longer the Web Cache url, but the AS url, so I'm basically bypassing the Web Cache).
I've solved the redirecting by modifying the httpd.conf on both AS instances. The other problems seem to have disappeared by magic. I've tried different configurations and somehow the one I have now works, even though it appears the same as a previous one.
There is a directive called UseCanonicalName which instructs Apache to use it's canonical name whenever it needs to construct a self referencing url. It defaults to 'On'. Changing this to 'Off' did the trick for me.