I have a Windows XP host that is running two VM's (Windows Server 2003) and the VM's are configured for NAT. Is there any way to make the hostnames of the VM's visible to the host OS without changing to a bridged network type?
Since your question is ambiguous, I will assume you mean "Can I access guests running on a host machine by using WINS hostnames?"
No, this is inherent to the way NAT works; a router handles unicast requests from the 'inside' of the router to the 'outside' (and the respective unicast replies in the opposite direction). Since WINS is a protocol that relies on broadcasts, which are dropped by the router, the host will never see WINS broadcasts from the guests. On a normal managed router, you could define rules that would allow the router to forward broadcasts, however neither VMware Server, Workstation nor Player allows you to modify the built-in routing logic.
Using DNS hostnames is not an alternative, since the router will need to have specific routes defined to forward traffic, this is also not possible with the aforementioned VMware products.
And a second NIC to your VM on the Host-only network, and use that.
Maybe if you tell us what you're trying to do we can direct you to the best solution? :)