I just posted this on the Icecast forum as well:

Well, it turns out not to be an Icecast or Nginx problem after all.

I tried it with Muse instead of Icegenerator, as well as mucking around with Nginx timeouts and proxy settings. Always the same problem.

Then it dawned on me that I had been trying it only with VLC as the client media player. So I tried with Windows Media Player instead. Lo and behold, it worked! It even worked when I put Icecast back to using Icegenerator instead of Muse, and with periodic metadata updates.

So it's a VLC problem. And an ongoing one, it appears. I upgraded my Win32 client box to the latest stable VLC (0.9.4) and on my Gentoo Linux/x86 box (0.9.10) and still the same problem with each.