There are several things that are easily forgotten when adding a new web part to a package, that can cause the web part to not show up in MSIE when trying to add it to a web part page. Typically the new .DWP file does not have 'Build Action = Content', or it is not added to Manifest.XML, or the SafeControls settings are not correct, or someting simple as a typo somewhere. And the new web parts are not added and are missing from the \WPCatalog\ folder when you run the STSADM tool.
I recently had to go to a customer to add some new stuff to a solution that had been implemented by someone else, and had just such a problem. The deployment script looked like this:
stsadm -o deletewppack -name Objectware.Lawyer.WebPartsSetup.CAB
stsadm -o addwppack -filename Objectware.Lawyer.WebPartsSetup.CAB
The package is first removed and then added by the above script, but my new stuff did not show up. I tried several times, and even watched \WPCatalog\ during deployment and saw that the web parts were removed and added, but not the new web parts. I ensured that it was actually my newly built .CAB that was deployed, but still no success.
I had never had this problem before, so I took at look at some deploy scripts I had made myself in other projects, and then I found a small, but important, difference:
stsadm -o addwppack -filename Objectware.MsCrmSales.WebParts.CAB -force
By adding -force to the STSADM command, my new web parts were successfully deployed to the SPS/WSS site. It seems that it is not enough to first remove, then add a web part package, to update its information in the web part gallery. The -force parameter is what actually makes it possible to reinstall a package.
From the WSS admin guide: Use the force parameter to overwrite an existing Web Part package with a new version, or to repair a Web Part package by reinstalling it.