Label all your cables!
It is most frustrating to work out the switch and port connected to the virused PC only to be told by the local site admin (who is on a different continent) that he doesn't know the physical location of the machine attached to that port and it would take hours to trace the wiring in his beautiful but undocumented wiring closet.
If your site is small and you know all the users and their PCs it's not such a big deal but once you have several hundreds of PCs in conjunction with managed switches it is totally irresponsible not to be able to locate a machine given the switch address and port number.
If each of your patch cables has the same unique identifier at both ends you can easily map (and then audit from time to time) your wiring closet's connections by noting the ID of the patch cable connected to each port of your switch and the ID of the patch cable connected to each port of the patchpanel connected to users' network outlets. (You DO have a map of where each of the users' network outlets are don't you?).
If your cable labels are barcoded the job becomes almost a pleasure!
Once you know where the ends of all your patch cables are terminated your computer can tell you what the links are - I use a perl script but just using a text editor's search facility you can easily work out where any given port is connected.
Of course it's usually too late because the anonymous cables are already in place. In that case you can build up a map by noting the network names and locations of any PCs that you touch so you have a correspondence between PC name, location, and - hopefully - network outlet number.
Then download the arp table from your router, the Mac Address / Port assignments from your managed switches and (as original poster is in a Windows shop) run NBTSTAT -A for each IP address (NBTSTAT is built into windows. A faster way is to run nbtscan but last time I looked it was not a builtin. I seem to remember I needed to install cygwin when I installed it on a Windows PC). nbtstat / nbtscan give you the correspondence between the Windows PC's name and its MAC address. Alternatively get this information from your DHCP server.
Given that information you can work out the correspondence between switch port and location without touching a single patch cable. I use a perl script but I'm sure it can be done other ways. Hint: If you have multiple managed switches the same MAC address may appear on different switches. For most switches that will be the uplink port connecting it to other switches. The switch which is really connected to the device should just have the one mac address on its port, or if there is a miniswitch at the user's end it should have fewer mac addresses on that port than any other switch.
Last thing. Visio diagrams are beautiful and really handy for top level stuff. However my wiring maps are ugly spreadsheets which allow me to extract the data and process it programatically. Much more useful.