Same situation here too, but lets make sure the following has been done.
Open the Exchange System Manager and navigate to Administrative Groups | your administrative group | Servers | your server | Protocols | SMTP | Default SMTP Virtual Server. Now, right click on the default SMTP virtual server and select the Properties command from the resulting context menu. When you do, you?ll see the Default SMTP Virtual Server Properties sheet. Next, select the Access tab and click the Relay button. You?ll now see the Relay Restrictions dialog box.
The Relay Restrictions dialog box gives you a choice of blocking relay traffic from everyone except for the domains or IP addresses listed on the exceptions list or only for the domains that are listed on the exceptions list. Which ever option that you choose, click the Add button to display the Computer dialog box. This dialog box allows you to enter an IP address or DNS name for a single computer, or an entire subnet address or domain name, which would apply to an entire group of computers.
Now, then we installed the same service packs as you did, so to answer your question Yes I believe it is a problem with the SPs I did the same damn thing on a SBS 2000 server and we are still working the bugs out. As soon as I get a solution to this little problem, you will be the second to know.
Let me know how you are doing when you get this.
best regards
Todd Kimbrell