I have seen 'relaying denied ' messages when the SME server was using the ISP email system. Horde works fine, but Outlook and other clients cannot be set to use the SME smtp service, they have to be set to the same ISP smtp settings as the SME server. Often involved installing stunnel on PC's too.
You can get issues if your ISP is using Office365 for mail systems and you try to use it as a smarthost (a lot have moved over to it as it means the ISP no longer has to host mail themselves, and for businesses accounts they probably get a kick back from their friends at Redmond for every account sold)
http://forums.contribs.org/index.php/topic,49452.msg247091.htmlI got shot of mine immediately