Well, digging in with Reflector, it seems to me that the Uri object contained in Request.Url is definitely built from the information that comes in from the request headers.
In light of that, I's suspect that maybe the requests coming in aren't what you think they are. Try having a look at the Raw headers in the requests coming into your server. I'd use a packet sniffer for this, I'd bet they reflect the problem you're seeing. If so, the problem isn't on your web server, it's somewhere in front of that.
Do you have any forwarding set up somewhere that could be causing this issue? Like http forwarding done by some sort of domain controller? Do you have any custom HttpHandlers that are massaging the request before handing them off? If you do, I'd look there. If you don't think you do, ask your Network Admin (if you have one) just to be safe.
All of this is a stab in the dark as I don't know your whole set up. But it's my best guess.
Good luck!