Is a Certificate required in order to setup Outlook Anywhere? or can you do without?

With Exchange 2003 you need to configure Rpc-Https, You require the certificate for the secure communication.

See this article on how to configure Rpc-Https:
http://www.amset.info/exchange/rpc-http-server.asp

Yes it does, but you don't have to buy a 3rd party one. You can use a self-signed one from your server.

It seems we need to rebuild IIS within Small Business 2003 in order for it to "self-assign" a certificate, any recommendations on a helpful link to do so?

"To re-assign a certificate in SBS 2003 - re-run the Connect To The Internet Wizard and change nothing until you get to the Certificate part, then name your certificate something like mail.yourdomain.com (or something that resolves in external DNS to your server's external IP Address), complete the Wizard and job done." - alanhardisty

That worked like a charm!  We created the new Web Server Certificate in just a few easy steps as you recommended.  We only have Outlook Anywhere being used on 2 computers, so no biggy.  We are just going to get on those two laptops and hit them webmail address and install the certificate from there.  

Our next step is going into Outlook and enabling Outlook Anywhere, then getting the settings right within there, from what I understand that is a little tricky.

Not majorly tricky - but worth reading the following:
http://www.amset.info/exchange/rpc-http.asp and / or
http://www.petri.co.il/how-can-i-configure-rpc-over-https-on-exchange-2003-single-server-scenario.htm
 

As long as you have the cert installed, the rest is simple in outlook.
Open up Outlook Mail Account Properties, click on More Settings> Connection Tab> Tick the "Connect to Microsoft Exchange using HTTP" tick box> Click on Exchange Proxy Settings Button.  Add the following:
Connection Settings - https:// www.yourdomain.com (or what you just named your certificate)
Connect using SSL - Ticked
Only connect to proxy server ........ - Ticked
msstd:www.yourdomain.com (or whatever you just named your certificate) in the box below
On Fast Networks, connect using HTTP - Unticked
On slow Networks, connect using HTTP - Ticked
Use default setting for Authentication.

Alanhardisty I assumed that was the end of the configurations, I am looking at http://www.petri.co.il/how-can-i-configure-rpc-over-https-on-exchange-2003-single-server-scenario.htm

and it looks like since we are running a Single Server we will need to:
Configure the Exchange computer to use RPC over HTTP/S
Configure the RPC virtual directory in Internet Information Services
Configure the RPC proxy server to use specific ports

I thought the configurations on the server side would be completed after setting up the certificate.

Alanhardisty, so i don't need to do what is recommended @ http://www.petri.co.il/how-can-i-configure-rpc-over-https-on-exchange-2003-single-server-scenario.htm ?

The Wizard should set everything up properly.
Test it first and if not - follow the article.
You could test on https://testexchangeconnectivity.com using the HTTP over RPC test but with a self-signed certifictae this won't work : (

My superior recommended not using msstd but just put in mail2.xxxxxxxx.com would you recommend using msstd?

Your superior can use whatever he likes - if you want it to work properly - use msstd: ; )

In case you want a walk-through - please visit:
http://www.msexchange.org/tutorials/outlookrpchttp.html
You can show your superior too - in case he does not want to take your word for it : )

It asks for a username and password for authetifcation after setting up the configurations. What is the properly syntax for that?
Just the Username?
The domain name/ username?
The Server Name / Username?

What?

Is there a certain port that needs to be open for authentification or?

We tried forward port 135 to the Server, still no sucess with authentification.

The logon credentials are usually in the format of domain\username and you will only need TCP port 443 open for this to work.
Domain being the internal domain name minus the .local e.g. yourdomain

Thanks for the help. I greatly appreciate it. I have a few other questions though I hope you can help with.

1. Is it a problem that my internal domain name does not match my domain for the FQDN?
2. This server was on existing other domain xyz.local. We created new email realm called abc.com. The internet domain name that is live is abc.com and the internal resolveds the server name to server1. My AD Integrated DNS domain is xyz.com. The server name is server1. I have a primary DNS zone set up internally for abc.com that has an A record for server1.abc.com that point to the IP of the server and a CNAME record mail2 pointing to that A record. Is that an issue?

Also, the server is SBS2003.  Does that make a difference?

SBS - not a problem.  SBS is only a license restricted bundle of Exchange 2003 and Windows 2003 Server.
It is quite normal to have a completely different internal domain to your external domain.  
For example, you would probably have microsoft.local as your internal domain and microsoft.com as your external domain.
The names of your internal / external domains are largely irrelevant.  As long as the FQDN you use to point Outlook Anywhere to your server resolves in External DNS to your servers External IP Address and the certificate name matches the FQDN, then you are good to go.

Thanks for eliminating that.  They weren't real but thanks just the same.  

This is the reason I asked the previous question.  When I set up the RPC over HTTP in Outlook internally and put my servername in as mail.example.com (My external FQDN) it quickly changes to the internal servername and stays that way.  Probably because it is just a CNAME record but I am not sure how to remedy this.  It DOES work internally but when I take it to an outside network it stops working because it cannot find that name because it is a .local address.  Likewise, when I change the settings when I'm outside to the FQDN it doesn't work either.  Not really sure how to continue troubleshooting.

If you have internal DNS for your external domain, this could explain the change to the FQDN, which should not be happening.
Why do you have your external domain as a zone in DNS?

Because example.com was the original company name.  They changed the company name and did not want to reconfigure the domain.  The new domain name is example2.com.  I added example2.com into their internal DNS because I wanted to be able to resolve mail.example2.com to the internal server IP when the clients were internal.  Bad idea?

I would not be adding your new external domain name to internal DNS (as a zone) as you don't need to manage this internally and hence the problems resolving.
Remove the zone from DNS, scavenge stale resource records and clear the cache and then clear the cache on a test PC, then on the test PC, configure HTTP over RPC to use the external FQDN and see if it changes.
To flush DNS on the client, fire up a command prompt and run ipconfig /flushdns.

So, we removed the zone from DNS, scavenged stale resource records and cleared the cache.  We then jumped to the test pc and used the FQDN (which ofcourse matches the certificate). No luck.  Furthermore if you ping the FQDN internally(on the domain) it gives you the same IP as if you ping the FQDN externally.  

I say "No Luck" because when adding a new profile (when on the test pc within the domain) within windows for mail, we are putting the FQDN into the Microsoft Exchange Server box and putting in our username into the username field and when we select Check Name. We get "The action could not be completed. The connection to the Microsoft Exhcange Server is unavalible. Outlook must be online or connected to complete this action". Thoughts? Recommendations?  

Thank you for your time.