I know the frustration. I never successfully used Home Sharing until I updated to iTunes 11. Since then, it works perfectly, even after I ripped my network apart, installed a new router and a PCI-E wireless network card.
Going wireless on the PC had an unexpected benefit. The Artist list was never complete on my old network but now displays properly.
I'm using Windows 64-bit Vista, by the way, so between Twerppoet and myself, we should be able to cover most bases in our quest to sort this out.