Just a question... why exactly are you looking to relay your email? Problems with your address showing up on "Dynamic IP" blocklists? Outbound port 25 blocked? What is the reason? Generally it is inbound port 25 that is blocked but you say you can recieve email fine so that is not your issue.
Unless you are having problems with your IP address showing up on blacklists you shouldn't need a relay service.