SQL Server Browser showing only hostname, not instance name

Question

I just setup a new Windows Server 2008 machine with an instance of SQL Server 2008 Express. The SQL Browser service does not appear to be working correctly. In Management Studio, browsing for servers shows the hostname of the new server, but not the instance name. When you choose the hostname form the list it doesn't connect. But I can connect manually by typing the hostname\instancename combination.

update 1:

1. The browser service is running, and I have tried it with several different accounts, including domain administrator which is a bad practice, but I tried anyway for troubleshooting purposes.
2. I have tried punching the appropriate holes in the firewall, and also completely turning the firewall off.
3. This is running on a Hyper-V, Windows Server 2008 32 bit guest, which is on a Windows Server 2008 64-bit host. I have done this before (without issues) on this same host, but with SQL 2008 Standard instead of Express.
4. When I browse for the server in SSMS(Express) on the SQL Server machine, it works fine and shows the whole instance name. When I browse for it on a remote machine (on the same intranet) with SSMS (standard) it just shows the host name.

update 2:

Followed the packets as suggested and found the following

1. The client sent the broadcast as expected and received correct responses from other SQL Servers on the same network.
2. The server received the broadcast but did not send a response.

Considering these results, I wonder why the host name ever appears in the client list in the first place. It shouldn't show up at all, right?

update 3:

Spent an hour and a half on the phone with Microsoft support. I learned a few things, but the problem is not yet solved. It was suggested that I try installing an instance of SQL Standard on the same machine. I did that and the new instance exhibits all the same symptoms. The hostname shows up in the browse list only once, not once for each instance.

update 4:

Stackoverflow chose an answer for me thanks to the bounty system, but this question is not answered. Today I tried moving the whole VM to a different host server - everything is exactly the same. The hostname still appears in the browse list, without the instance name.

update 5:

Confirmed that Hyper-V Integration Services are installed on the guest (SQL) server.

Answer 1

check that the browser service is running, it's not turned on by default.

UPDATE1: See if you can install Network Monitor/Wireshark to do a network trace on the SQL Server to see if it's receiving the broadcasts and sending responses. I think this is your best option in troubleshooting this issue. According to MSDN the service uses UDP port 1434, so this is the traffic to watch.

UPDATE2: Does the server have multiple IP's? according to this MSDN article the Windows Server 2008 firewall has issues responding to SQL Browser service broadcasts, even with rules allowing packets through.