Yep, not a SME problem at all. <fx="sheepish grin">In fact, the problem is half my stupidity, half my ISP's shortsightedness. They block all outgoing SMTP traffic except through their mailserver, therefore my telnet to port 25 didn't go through. </fx>
So there you have it. I tested from a host on a more enlightened ISP and voila, SMTP.