Recently my Google-toolbar has gone mad. Without any reason it started to display all my deleted bookmarks, even those that were bookmarked by accident and removed ages ago.

One more witness that Google never deletes stuff.