What you want is called Microsoft Application Request Routing 2 (ARR). (Maybe the clumsy name is part of why so few people know of its existence?)
Microsoft ARR is a free-of-charge HTTP layer load balancer, implemented as a module for IIS 7+. (ARR itself is gratis, but the Windows Server license is of course required for the underlying OS.)
Since ARR is just a thin shim on top of IIS, it is quite fast and absolutely robust. And administrating ARR will be familiar for you guys, since you're already an IIS shop. ARR just installs itself in the IIS Manager GUI.
For a true high-availability setup, you should combine NLB and ARR, so that NLB keeps the ARR server tier highly available, and ARR keeps the backend web server tier highly available. See Microsoft's docs, and see the long list of documentation at the end of the ARR overview page linked at the top.
The only real downside to ARR is that if you do true high-availability, then you will require at least 2 Windows Server licenses & physical servers. Given that, and given the time it takes to set up, then low-end load balancer appliances like Coyote Point or loadbalancer.org can sometimes be a cost-effective alternative (Or Kemp, Barracuda Networks, or any of the other low-end vendors).
ability to seamlessly take a web server out of the load-balanced mix for maintenance without interrupting users.
That will depend on how session state is handled, i.e. how your backend servers share or not share the "this user is logged in" information.
If the webapp tier is stateless (i.e. placing session state in a shared datastore, fx a shared RAM cache or MSSQL), then you can just pull a server out of the pool. If not, then you can use "sticky sessions" on the load balancer, and remove a backend server from the load balancer pool, and then wait until all users have 'drained off' the server in question.
Willy Tarreau, the author of HAProxy, has a nice overview of load balancing techniques and issues here.
Many modern reverse-proxies could alter the query-strings.
But i see no reason why a load-balancer or proxy will do that by default.
Maybe it uses the URI for sticky session load-balancing, but that would be really stupid.
So: No, i don't know any load-balancer, altering the uri and the parameters by default.
Best Answer
You could accomplish what you need by putting your app servers in a private subnet in a VPC, which routes 0.0.0.0/0 to a NAT instance in a public subnet. All requests to the 3rd part service would appear from the NAT's external IP (assign an Elastic IP to keep it consistent).
The NAT will be a bottleneck for these requests, so you'll need to make sure it's adequately scaled. If you have 3 IPs you could whitelist, you could put your app servers and NAT devices across 3 AZ's with a separate NAT instance in each AZ.
http://docs.aws.amazon.com/AmazonVPC/latest/UserGuide/VPC_NAT_Instance.html