A couple of things. First, admin like a pure Exchange Server. It is one, for the most part, but the wizards have been set up to make things easier and to keep several moving parts in sync. You were asking for a "really quick way of doing it" and it's in the wizard.
Second, MessageLabs may require an SSL connection or authentication, and the KB article doesn't tell you to do that. I think the wizard may give you the option to supply creds. Skim the MessageLab docs again and see if it mentions authentication. I use several different outside mail scrubbing vendors and none require authentication.
Third, using a smarthost will still allow your server's name to show up in the header, it will just add an additional header for the smarthost, so you should see both MessageLabs and your server's name in the header when the email goes out. If your server is having trouble authenticating or reaching MessageLabs, then it will send the mail out on its own, but it will ALWAYS send to the smarthost first.
Check your Application log for errors related to relaying through the MessageLabs server. If there aren't any, go into the Exchange Admin, get properties on the Servername, and go to the Diagnostic Logging (or Monitoring?) tab. From there pick MSExchangeTransport on the left and turn SMTP Protocol Logging on Maximum on the right. Send out some more mail and check your App log again to see what activity was generated.
You may see that MessageLabs is rejecting the attempt to relay, in which case you will need to communicate with them and make sure that your sending IP is in their database. They will usually need that to allow outbound mail from you.
Dave Shackelford
Shackelford Consulting