Sort of a follow-on to #5.
Starting with Vagrant 1.6.x, there is a global index of all active machines. It might be useful to have a command like vagrant autonetwork purge that only runs under 1.6.x and newer and de-allocates any IP attached to a machine that is not registered in the global index.