I have just deployed Exchange 2010. I got a valid certificate and installed i on my Exchange Server. I confirmed that it was working internally (No certificate error when connecting to OWA from IE inside the network).
All that was left now was to install the certificate on my ISA server. Here is the trick:-
Do not just type certmgr.mmc in the run command. This open the certificate manager for Personal certificates.
You want to install the certificate for the computer. To do this, type mmc in the run command. Then add the certificate managed it there. Here you will be asked if you want the certificate manager to manage User Certificates or Computer. Choose computer.
Big thanks to Law for this!