Recently, someone asked the following question on an internal Microsoft distribution list:

Can someone please outline the ways in which Exchange 2003 is dependant upon WINS..?

Here's the answer I wrote back:

Exchange 2003 is dependent upon three different things that are related to WINS:

1) DNS resolution of "short names" - i.e. there are places in the Exchange 2003 code where it uses the standard DNS resolver libraries to look up things like "japansvr04", and the DNS resolver appends the DNS suffixes, which may help it find the item, which may be "japansvr04.corp.company.com".  For instance, we store servers in the AD as short names, and use that name in many places, including in the admin GUI code.  In order for this type of lookup to work, you need to ensure that the DNS search suffixes are set correctly on your DHCP servers (or on the servers themselves if you aren't using DHCP). 
2) NETBIOS Name resolution of "short names" - i.e. there are a smaller number of places in the code where it uses specific NETBIOS APIs that do not append the DNS suffix.   This includes setup, some cluster-related setup/admin, and some Exchange System Manager code.  In order for this type of lookup to work, you need one of two solutions:
a) Netbios name resolver - this is a service that uses subnet broadcast to let you find the IP addresses of other hosts on your network, based on the name.  This is what lets me, on my desktop machine at home, type in \\server\videos and see the share from my server, without any DNS or AD setup.  This works fine but only if all of your admin consoles and servers are on the same subnet!
b) WINS - this allows netbios name resolution between machines on multiple subnets
3) Uniqueness of "short names".  WINS enforces that all short names are unique within the set of domains/servers that use the WINS servers.   Exchange 2003 stores config info in AD by shortname (think of it as the foldername in the Configuration naming context in the AD) - if you were to have two different servers with the same shortname (but unique FQDNs) and try to put them in the same Admin Group, I'm not sure what would happen - I know it wouldn't work!
 
In Exchange 2007 we are fixing the first 2 of these. (we can't fix the third one in order to have interop with Exchange 2000/2003).  We have code in the pre-requisites check to give you a nice error message if you try to install a second server with the same name in the Exchange org (since all 2007 servers are in the same AG).
Obviously if you have any pre-2007 servers around, you have to keep WINS around.
 
You can also find more information in this KB article: http://support.microsoft.com/?id=837391