This issue stands for hotmail as well. On my N95 emails deleted on the phone (when selected to be removed from server) were removed from my email account and vice versa. Whether or not POP3 is supposed to support this is another matter, the N95 and other Symbian 3rd phones managed as do all desktop POP3 clients I've used so I'm not sure why the N900 can't/doesn't.

MS don't provide IMAP servers alas and using anything else is an inconvenient change right now.