I've just suggested this same answer on MSDN:
This stsadm helped me in finding where the webpart was referenced in any way:
stsadm -o enumallwebs -includewebparts > C:\temp\somelog.txt
Then you can see the web part is listed under some <Web Id=... Url=...> XML node, i.e. you know the "culprit" web site.
At that point, some reasons I've found for those forgotten references:
the webpart is used in some sub-site of the culprit website, and the sub site is hidden from the quick list or top bar
the webpart has been deleted from the culprit website, but it still is in the "site collection recycle bin". You can reach that by going to the normal website recycle bin, then look for its link on the top bar description ("Use this page to restore items that..."). By the way, this site collection recycle bin has two views itself: be sure to check them both.
In both cases, I got some help by browsing the culprit website with SharePoint Manager. With that I could easily spot the existence of a forgotten subsite, as well as the existence of this "second level recycle bin".
HTH