I have tried everything that supposedly clears my cache and it hasn't worked. Including a clear cache button. Well, I noticed something recently. This only seems to happen when I hover over a bookmark folder with TONS of bookmarks in it, or open up the downloads box and I haven't cleaned it up recently. So, really we need an addon to clear whatever cache holds all of the website icons displayed in our bookmarks or clear that memory sector up or whatever.
What are you seeing in your cache that you want to clear? Please note that cache (stored files) and history (stored URLs and visit dates) are kept in two different places.
Bookmark icons should be stored with your bookmarks (they are converted to a string of text). I don't think you really need to remove those, and actually, I'm not sure how you would without exporting bookmarks, flushing them, and re-importing them.