I have a problem similar to this:
This is with IE 8
When I do a Google search, I had the Safeweb icons next to each url listing. I noticed this is missing and not related to my recent upgrade to 2011, since they were not appearing with 2010 either. I had done a registry cleaning end of August and thought that may have been the reason.
I used Norton Removal Tool (once) and uninstalled my NIS 2011...reinstalled and same problem. Yes, Safeweb is enabled in the toolbar.
Interestingly, it is working in FireFox browser.