Try disabling all the transparency/noiconborder type patches and settings you have, and give Birdie2000 a go instead. Unlike NewIcons and DOpus Magellan, it flood fills the outside of an icon with the transparency, rather than simply replacing pen 0 with transparency. This means that if you have an icon that uses the medium grey pen somewhere in the image, it won't appear transparent over a background image, only the outsides of the icon will be transparent.
http://aminet.net/package/util/wb/birdie2000
