What I would do:
1. Right click on the application you want to replace the icon for – click ‘show package contents’
2. Look in ‘Contents’ > ‘Resources’ – the Icon file is usually specified in here (and usually a .ICNS file)
3. Click to rename that file, First copy the existing name, don’t forget this, and rename it old_icon.png or whatever.
4. Paste your new desired icon into this folder and give it that old icon’s name you’d copied – so that it’s called what it should be to be called for that particular app.
5. Make sure you keep a backup of all the nice icon’s you’ve downloaded as chances are if you upgrade the app you’ve customised it will lose its custom icon and you’ll need to do this again – I keep a whole stash seperate from my apps.
You don’t need to do this for all apps, just the stubborn ones.
Bonus ball: Check out this bundle of apps for converting and managing icons, to make your own custom icons easily etc. Note that some of them won’t create Leopard-friendly 512×512 icons, but I find I can survive without those most of the time!