Use with non BT mail addresses

Having successfully used BT Broadband for the last couple of years with no issues, I am suddenly unable to send e-mails from Outlook and Outlook Express for e-mail accounts that are not on BT domains (eg @.virgin.net) - receiving e-mails still works.

Technical support say that I'm lucky to have been able to send mails for such a long time.

Is anyone aware of a solution to the problem? Failing that, are there broadband suppliers out there that don't block outgoing e-mails that aren't from their own domain accounts?