I have exactly the same problem with Windows Mail in Vista Premium Home
edition on a new Acer laptop. The preinstalled version of Norton was causing
the problem with the deleted mails (turning off outbound scanning helped, but
there's obviously an AV compatibility issue here). The restarting Win Mail is
driving me mad, so if anyone has a solution that would be great!