In order for the Windows hostnames to show up in ARD you need to have a DNS server that is setup to allow dynamic updates from client machines so that the Windows machines can register their name with the server. You could manually update your DNS records for all hosts if you have static addresses -your DNS should be setup with some default-style name resolution to aid readability anyway. But, since most admins use DHCP for their client setups, a dynamic DNS server that is properly configured will allow this to happen without admin intervention.
It is entirely possible to do this with the ISC BIND server or with a Microsoft DNS server. You would then not need BonJour -which is intended for service broadcast and discovery and which can also be configured with a dynamic DNS server- installed on the Windows clients for name resolution as that functionality would be duplicated by a service that runs natively on Windows.
There is an additional benefit of DNS-based Service Discovery to Mac clients in that any service that is running on a server or client can be discovered by BonJour capable apps like iTunes or Safari once it is properly configured on the DNS server, especially if you are working with a highly complex, multi-subnet, network. A working solution for your issue can be found here:
http://www.dns-sd.org.