Cannot Send Mail Through VPS SMTP Server. The Usual Fixes Didn't Work.

Over the past week, the SMTP server on my VPS has been hanging whenever I try to send an email from my computer. It'll eventually work again, but now it's been down for the count for about 18 hours. Tech support keeps on recommending minor fxes and issuing standard responses like "try disanbling your firewall" and the like, but nothing works. I have already told them this:

* I know _you_ can probably send POP/SMTP mail through my server. I can't.
* Mozilla Thunderbird will connect and send mail through other
POP/SMTP servers.. Not my server here.
* I can connect to _receive_ email, but I can't send it.
* My ISP (SBC/AT&T ADSL) does not block outgoing mail to port 25 on my account; I had the block removed.
* I've got an exim server running on port 26, too. Doesn't make a difference.
* I tried connecting from another ISP (my work PC). Still can't send mail.
* I tried using IP addresses instead of my domain name. Doesn't work.
* I didn't change any account names, passwords or anything like that.
* I tried other email clients. Can't send mail with them, either.
* The exim queue has very few messages in it. Clearing the queue didn't work.
* I disabled firewalls. Didn't help. Besides, I was able to connect
to other mail servers - just not my VPS here.
* There are no typos in any of the account or general configuration settings in my client. Nothing changed. One day I could send mail, now I'm having problems.

I keep saying this, and keep attaching entried from exim_mainlog with error messages like this PROVING that I can't send mail:

2007-02-01 08:26:00 H=adsl*****
[*****]:1294 I=[*****]:25 incomplete transaction
(connection lost) from for
*****@gmail.com
2007-02-01 08:26:00 unexpected disconnection while reading SMTP
command from adsl*****
[*****]:1294 I=[*****]:25
2007-02-01 08:26:17 SMTP connection from [*****]:1344
I=[*****]:25 (TCP/IP connection count = 1)

2007-02-01 08:29:34 H=adsl*****
[*****]:1344 I=[*****]:25 incomplete transaction
(connection lost) from for
*****@gmail.com
2007-02-01 08:29:34 unexpected disconnection while reading SMTP
command from adsl*****
[*****]:1344 I=[*****]:25

Any ideas? I think tech support at my end has given up; it's been hours since I last heard from them, and that was just to say that they updated everything to the current version, and disable the firewall. (Again!) Didn't work.

So, before I pack my bags and find another VPS host, what should I do? Having outgoing SMTP email is a MUST; not having it is a deal-breaker.