When the machines get an IP address via DHCP on the network, do they not get DNS as well?
eg. you should be able to connect to them via their hostname, which would stay static.
You could run all the virtual machines within their own "Virtual Network" and run your own DHCP/DNS/router which connects to the real network, but you'd still need your network admin to add route/dns forwarding which he might not like.
The other way of doing it, and which would leave you in some control, would be to cheat and use one of those external dns services. eg:
dyndns.org is a free service that lets you have a static hostname that gets mapped to a dynamic IP address. They also have a tonne of clients for various OS's to keep this upto date. Usually, you'd have this set to an external address (eg your home router) so you can just remember
myhouse.dyndns.org rather than
126.96.36.199 or whatever its changed to recently.
In your situation, I would do similar for each of your virtual machines. Set yourself up an account and get a hostname for each machine. Install the client tell them to keep updates. So you end up with
myvirt1.dyndns.org and it points to
192.168.x.x or whatever IP you've just been given.
-saying that, could you not just ask your network admin for a block of static address's?