I know I had a similar problem with my new ISP, basically I set up an email address prior to been fully connected with them. Basically I applied to them for my service, but in the mean time I set up some new email addresses with my new to be ISP, I could receive emails to my newly created email address but I could not send from it. When I enquired to why this was to my new ISP, I was told that,
"The outgoing mail server won't allow you to send out until you're connected to ourselves, as it's validated by your IP address"
Seems a bit of a long wait 4 days for a reply though, it may be worth emailing them again to try to speed them up.