Sent plusnet emails aren't being delivered

[#1]

Can anyone help?  I have just set up outlook for a client, and although we are receiving mail, and the sent mail disappears from the outbox, it isn't being delivered.  No error messages appear and no non-delivery messages are received.  I have checked with Plusnet, who seem to think it's the anti-virus (but suspect this may be a standard reply), I'm not convinced.  Any ideas?

[#2]

May or may not be relevant, but I sent an email at 22:02 11/03/10 (yesterday evening) from Plusnet to *****@waitrose.com and it has still not been received. Knowing that it had not, I resent it at 09:29 this morning and that one arrived within a few seconds. The "missing" email appears to have been sent succesfully and I have received no bounce or error message. If the recipient had not talked to me this morning I would never have known of the delivery failure.

[#3]

Hi, thanks for this, I'll try to send a message via webmail today and see if it gets delivered.  I'm not convinced that it's anything to do with the antivirus since that would leave the message in the outbox and probably generate an error message- what do you think?