I can Command+K in Finder on my Macs and connect to my Windows HTPC via
smb://mediaserver. But if I use the Mac Remote Desktop client and try to connect to that PC via its name
mediaserver, it can't find it. Why not?
You probably need to install Windows Bonjour services from Apple. This allows your Windows workstations to participate in the mDNS name resolution Mac uses by adding an mDNS Responder service to your workstation.
The Bonjour mDNS Responder service to announce your Windows system on the network should be available in the download from https://developer.apple.com/bonjour/
It also often is one of the components installed by Adobe Creative Suite.
I know when installing iTunes for windows there is an app coming with it called "Apple Software Update"
This will list the updates available for apple software on your win PC, next to the available updates it also gives you the opportunity to install additional apple software on your windows pc, including bonjour.
Or you could take a look at this, this may work as well: http://support.apple.com/kb/DL999
Description of bonjour: