John,
I've had to do this before. Basically, you can make use of the URL property of the web reference, as follows:
Assuming that your client piece has a web service 'proxy' class reference...right before you make the call to your web service, you set the URL property of the web service reference to whatever the URL is. Once you do that, any calls to your web service should go to the appropriate location. I've had to do that where the client piece was run by users who were connecting to a URL that wasn't defined until runtime.
So with this approach, you only need one web reference, as opposed to one for each possible URL.
Hope that helps,
Kevin