The Computer Browser service is what runs what you see in the Network Places window. Computer Browser works on the same segment only; it does not route through a gateway.
So, with the different VLANs set up, then they aren't gonna route the browser elections the Computer Browser service does to figure all this stuff out.
WINS would be a lot better way to handle this, and I am confused on how you "got lost" setting it up. Just install the WINS Server on a Windows Server (NT4 Server, Win2K Server, Win2K3), and then in the Primary WINS Server field on the IP properties of each XP machine, put in the IP address of the WINS server.
Then on the XP boxes, run this command from the Command Prompt:
nbtstat -RR
(yes, it's case sensitive)
That will force the XP boxes to register themselves with the WINS server.
After a while, that should clean things up.