I seemed to have been having this same issue. Deleting a post visually worked but, refresh the Manage posts page and the post magically re-appeared.
However, I fixed the issue by disabling each of my plugins, created a variety of new temporary posts, and then deleted the new posts one-by-one after reactivating plugins one-by-one. This method of elimination allowed me to find that there was a plugin, Google Sitemaps 2.7.1, that was creating this issue. This plugin, btw, was also causing a blank page to appear after creating a new post…I think. Anyways, if any of you are running this plugin, you might try disabling it. If not this plugin, then you might try the same method of elimination with your other plugins. Post back if my explanation didn’t make sense.
Thanks,
J