Symantec basically coerced us into buying a code-signing cert from them, and we still had to submit every build directly to them for this reputation issue to go away. Royal pain in the ass.
Same deployment procedure as had been for years (we'd previously been code-signing with a GoDaddy cert) with Click-Once deployment (was a .Net Office add-in), all of a sudden we start getting dinged.
The cost to the company (a relatively small company) was significant. Had to buy a Symantec code-signing cert (~$900), had to ditch ClickOnce and invest in InstallShield (don't recall the license cost) and engineer the installer to both sign the installed libs & the installer itself. All of this because Symantec hadn't seen the new libs enough because, well, we targeted a smaller corporate audience (for argument sake, we had around a 100 clients, of which, each would only have 1 or 2 installs of this particular app).