Key Update Tool throws an error

Note to self:
If Key Update Tool (A tool to update Win XP Serial Key) is giving you this error:

The product key could not be updated on your computer.  This may be due to technical difficulties or network connectivity issues.  Please contact Microsoft Support for additional assistance.

 Make sure you have turned off Trend Micro antivirus.*

*May apply to other antivirus software as well.

Outlook on Exchange using wrong certificate

 Many of us encountered this error:

The name on the security certificate is invalid or does not match the name of the site.

But this time, it was something different.

Not my image, but the exact error. (Source not found)

99% that it's not the solution you are looking for. But I will still fill the gap for the 1% that may encounter it.

I will explain every step I did until I found the problem. There are some solutions that I've tried that didn't work for me, but might for you, so you may try them.
*If you don't want to read it all, just jump directly to my solution down below.

The System:
SBS 2008 (server 2008 + exchange 2007)
*The solution may also apply for greater versions of exchange.

The problem:
As we began upgrading people to outlook 2010 there were errors popping about the certificate.
So the first thing I did was issuing a certificate from GoDaddy and installing it using the SBS console.
It didn't fix the problem.
The server is pretty old, and it wasn't me who installed it in the first place and it wasn't me who maintained it for several years, so I decided to go the manual way.