Weird email problem with RoadRunner

Here is my problem:

I can receive email, browse the internet and read newgroups, but cannot
send email. After clicking on "send", email program hangs, and
sometimes after about 1 minute sends email, sometimes I am getting a
message that email cannot be send.
I have few PCs connected to the Internet through a router. This problem
is on every PC. Some PCs use Win, some Linux, some use Outlook, some
use Eudora, Linux uses KMail - but every PC have problem sending email,
but no problem receiving email or browsing the Internet.
I disconnected router and connected PC to the Internet through modem
only (PC with Win) - I had the same problem. I tried TRACERT to email
server (pop and smtp) - response time bellow 10ms. Called tech support
- they have no similar complains from my area.
Any ideas what else I can check?

Thanks,

Zalek