i have a user who deletes emails from his 8800 and the device asks to confirm delete - he picks yes but the email remains on his blackberry inbox. hide filed messages is set to yes.
i've not pulled the battery - don't know why cause that usually the first order of business... i'll give that a try.
there are no bes restrictions against removing emails or at least there were none before - he could delete emails i swapped his device out for the 8800.
I had a similar problem with calendar, when I deleted the whole calendar DB thru DesktopManager. The Cal was wacky (could view stuff but not delete it) until I rebooted the BB.