Outlook Emails are Sent but stored in drafts (Not what you think)

Question

I work in a corporate environment (6,000 users). We have 1 user whose Outlook 2007 mailbox is acting up.

If the user writes an email and sends it before the Autosave feature kicks in, the email is sent.

if the user writes an email and it takes longer than Autosave (3 minutes) her email is saved to drafts. If she send it, the email is sent but the email will no delete from the drafts folder.

The Backstory

The user was accidentally deleted as an current employee. (In our environment you are never actually deleted, your account is just sent to a 'recycle' bin.) After the user was restored, about 2 weeks later, her machine was due for replacement. The machine was replaced and that is when the errors started appearing. Additionally her maiden name from 4 years ago showed up in office communicator.

If the user logs into a machine that she logged into previously BEFORE her account was 'deleted' no issues exist.

If a user logs into a new machine, the problem returns THEN the problem happens to any other user that logs into that machine after her. (But it doesn't follow them to other machines.) It only happens to her. Whatever machine she logs into, Outlook breaks.

An error message she receives when attempting to delete the email in the draft folder is "The Operation failed"

When autosave pops up: "Outlook has automatically saved a draft of this message. Do you want to keep it?" she clicks NO, the error pops up "The item cannot be moved. It was either already moved or deleted or access was denied."

The user has been issued 4 new machines with our standard corporate image on it. Problem follows her.

CRY FOR HELP

This problem has been going on for two months. It has stumped all our best Exchange, AD Engineers, PC Support issue, Outlook specialist.

Anyone ever encounter this issue?