if you want to deploy the VMs on different computers talking to each other, you need to sysprep the VMs otherwise you will get problems.
Making a catalog is quite a good idea.
Don't you have the possibility to leverage Hyper-V with self-service portal to deploy VM on demand ?
Another good solution for this is to leverage a VDI solution