Try loading MS Outlook on the server (Outlook 2000 for SQL Server 2000), and set up an Mail Profile for the login which the Server Service uses. You can then test the MAPI separately. Now select that Mail Profile and test. Remember that if any changes are made to the MAPI settings you must restart the SQL Services to activate.

If you are still struggling, and only require out-going mail, you could try using SMTP through CDO. See Clinton Herring's SMTP Mail Stored Proc at http://qa.sqlservercentral.com/scripts/contributions/510.asp.