After edit: interesting little bug. I have confirmed that I can see a favicon from my site served up with a custom 404 message in Firefox, Opera, and Chrome, but not in the latest version of IE (which I use only for testing for little bugs like this). Quite odd.
I tried with different settings—even putting /favicon.ico on the root and omitting <link /> didn't work.