This happens to me occasionally with my Lineone, (Tiscali), address. Only happens with Tiscali, never the BT one I use as my main address. Perhaps your ISP has the same "blip".
I just go to the Tiscali webmail site, and delete from there. I use Outlook also, with the same setting.