Some thoughts on your post:
1) You don't say what you are using for spam control so I don't know your specifics. I doubt if that is what is not causing you to be able to relay though. You can try turning spamassassin off from the command line to give it a try: "service spamassassin stop". Then see.
2) As far as things to look for in Sendmail. If everything is entered correctly in the access database you should be able to relay from external source. Make sure that you have the syntax correct though because it is very picky on it being "just so". Also, make sure that you rebuild the database and then restart sendmail after you are done. Try the man pages or the docs on sendmail website for the exact syntax. I believe that it is " makemap hash /etc/mail access < /etc/mail/access" . That should rebuild the database.
3) Make sure that your firewall isn't keeping you from accessing the server. You will need to have ports 25 and 110 open (if you are using the defaults). I believe that there are some others but make sure those are open.
4) I would assume that you are NATed behind some kind of router? If so, make sure that you are forwarding those ports (25 & 110) to the interior IP address of your server.
5) Don't allow unrestricted relaying to your server. If you do then you will end up on one of the websites that post all the open mail servers that all the spammers are using and most folks (like me) will shut down your mail server having access to their users. You will have to constantly monitor your server to make sure that spammers aren't accessing it from the great beyond. They will use ports all over the place and you will have to make sure that they are closed. So, it becomes a "you against them" thing. It requires diligence, but can be done. I had a spell here about two weeks ago that I found some trying to relay. Every time I shut them off from one way in, about an hour later they would find another until I had it so locked down that my anti-virus software couldn't update itself. Had to back off a little
6) On that point, make sure that you do run a good anti-virus program. I personally use Vexira. It's a commercial product but it does a good job. I haven't had any problems so far (knock on wood). I use a two tiered approach: I run Vexira on my mail server and then Norton System Works on my Windows clients. The two of them seem to work well
Check on these things and then repost if you are still having problems.