So what's the trick?
The way OS X stores custom icons is by having an actual icns file on the volume. That icon is a dotfile, meaning that its name starts with a dot, which traditionally means it should be invisible. You can copy icns files into target folders and volumes under the names they are expected to have simply by using the Terminal. Open up a Terminal window and do the following:
cp /path/to/icon.icns /Volumes/volume_name/.VolumeIcon.icns
So if you have a stubborn icon that just doesn't want to be applied, there you have it, a solution.
[robg adds: Note that if your volume name includes a space, you'll either have to place the second part of the above command in quotes, or escape the spaces with backslashes.]

