Same happening to me: I delete the logo and depending on the template I see either the logo appear again or an empty frame signaling logo not found....

When this happens, the logo is being cached by the browser. The first thing to try is simply pressing "Reload" or "Refresh." (this usually works in IE and firefox). If that doesn't work (Sarafi, typically), then you'll need to clear your cache.

The logo is being deleted from the server, but your browser simply isn't asking the server for a new copy.