Hi,
You are correct in that you cannot have to site bindings with (*) on port 80 running at the same time. This is what binding host headers are used for. Essentially you create DNS records and "bind" then to port 80 and the dns name.
ex:
site1 with host header mail.domain.com on port 80
site2 with host header domain.com on port 80.
each site will not use (*) on port 80 anymore.
Now to combine them, I have not played with SP2010, but with SP2007 And WSS 3.0 all you need to do was remap the Virtual directories under the other WebSite that Exchange is on. I did this manually with 2007 and had no issues.
If you have problems, I'll grab a release from MSDN and test it up.
-Hades666