I tried removing it by using the regular utilities like ad-aware, but it doesn't do much good.

You should contact LavasoftUSA and tell them about this. I'll bet that with some tweaks to ad-aware they can remove those as well.

Doesn't solve your immediate problem, but worth reporting to them nonetheless.

To get rid of right-clicks on the Explorer menu, search the Windows System Registry for a substring of the text that appears in that menu. It will be under the "Shell" entry, most likely in more than one place. Delete those entries and you should be golden.