First off, I tried to import the certificate using OWA. Connecting to the HTTPS URL gave me the usual certificate warning, however importing the certificate into Trusted Root Certification Authorities Certificate repository, didn't fix the error. I ignored this at my peril, and tried to configure Outlook 2003 as usual, but Outlook anywhere refused to connect.
This Post on the Technet blog, should have worked, but it didn't.
I opened up a Certificate MMC and noticed that the current user did indeed have the correct certificate installed under the USER Trusted Root Certification Authorities, but not the MACHINE'S Trusted Root Certification Authorities.
Once I imported the cert into the Certificate store used by my local computer, everything started working transparently. OWA stopped bleating about having a untrusted Cert, and Outlook Anywhere 2003 started working immediately.
The short and sweet of it is, that if importing the SBS self signed cert into the local user's Trusted Root Certification Authorities store doesn't work, try importing it into the Local Computer Certificate store, instead of just the Local Users store.