I have been through many q articles describing how to secure exchange
5.5 against relaying.  I have also performed open relay testing, and
most of the tests do come back with relaying prohibited.  I am using
www.spa-mail.com for testing.  I still get items in the application
event log on my windows 2000(SP4 + Updates)/5.5(SP4 + Updates) server
indicating that message delivery attempts to foreign domains have
failed for various reasons including the mailbox has moved, the
recipient is unknown, message size is too big, etc.  This would
indicate to me that UCE messages are in fact being delivered.  How do
I secure this exchange box against relaying.  Please do not merely
provide me with a list of links, I have been through them.

There are two places for you to make configurations to ensure that you
aren't an open relay. From the sounds of it you are already configured
properly and the messages you are seeing are probably the bounce
messages that your MTA is sending to the spammer to let him know that
relaying is not allowed.

The two places you make changes are:

On the routing tab: ensure that only the domains that your server
should be accepting mail for are listed here. They should also likely
only be configured as <inbound> if your exchange system is going to
accept mail for them.

and on the routing tab there is a routing restrictions button. Click
that and on the window that opens ensure that only the subnets for
your internal networks are listed here. This area controls who can
send mail to any domain on the internet, so you want to make sure that
the only subnets listed here are the ones who should be using your
SMTP server to relay which should be only your internal networks.

I know you didn't want a link, but here is a good one anyway. You've
likely already seen it:

http://www.microsoft.com/technet/security/prodtech/mailexch/excrelay.mspx

Again, if you have followed those two steps and a couple of anti-relay
sites say that you are ok then I believe you are fine. Those messages
are likely just the bounce messages from your MTA not allowing
relaying.

The first thing you need to do is to find out if it is possible for
someone to relay a message through your server. One way of doing this
is from a telnet session to your Exchange server on port 25, which is
the port used by the SMTP service. If you are testing from an MS
Windows computer, type telnet in the Start menu and open a session as
shown in figure 1. Of course, you'll need to supply the name of your
own server instead of 'SRVR-1'.

type Open SRVR-1 25

There are only two commands that you need to enter to find out if your
server is an open relay. You need to pretend that you want to send a
message to a different domain than your own email domain, and that it
also originates  from a different domain. This is done by entering a
mail from: command followed by a rcpt to: command

mail from: me@bogus.com
the replay will be 
250 Ok - Mail from <me@bogus.com>
then type
rcpt to: you@bogustoo.com
you should get the message 
550 relaying prohibited however if you get 
250 Ok - recepient <you@bogustoo.com> 
you are relaying 


The method described here relies on your Exchange server having either
Service Pack 3 (or later) installed, or Service Pack 2, with the
Post-SP2 Hotfix. If you have not applied the service packs you can
only prevent relaying by making some changes to your system registry,
and this method will not be described here. It also relies upon your
not having deliberately specified IP addresses for relaying.

Quit Telnet and open the Exchange admin program , expand the tree
untill you can see the connections container , double-click the
Internet Mail Connector to open its property pages and then click on
the 'Routing' tab to reveal the
Routing property page

It is quite tempting to select the option labelled 'Do not reroute
incoming SMTP mail', since that sounds like what we are trying to do.
Unfortunately this option does not work as well as you'd hope, since
spammers have found ways of formatting email addresses that can bypass
this configuration. What we actually have to do is play a small
'trick' on the IMC. Make sure that the 'Reroute...' option is selected
and click on the 'Routing Restrictions...' button

The trick that we are going to play on the IMC is this; we select the
option labelled 'Hosts and clients with these IP addresses but leave
the table empty  as shown above. This configuration is not documented,
but luckily for us it changes the behaviour of the IMC in the way that
we require.

Click the 'OK' buttons to close the IMC property pages altogether.
Note that you will need to stop and restart the MS Internet Mail
service using the Services applet in the Windows NT Control Panel
before the new configuration is activated.

Having restarted the IMC, we can now use the telnet utility once more
to test our new configuration

Hopefully, this time you will see the response 550 Relaying is prohibited 
If so, you can be sure that your server is now secure against third
party relaying. Of course, it is a good idea to make sure that you
look out for new system vulnerabilities. It is possible that one day
the spammers will find a way to circumvent this configuration. They
can be very determined.