The mails that don't get deleted from the server were probably downloaded before you installed avast. When avast Mail Protection Wizard modifies your account (I suppose we are talking about Outlook Express), OE resets its internal counters for that account and forgets its 'history'. I think that if you delete all mails from your mailbox now, it will then work as before.