I would hope that your contract didn't state the customer was guaranteed the
same IP for eternity; if so, your legal department needs to be hanged. You
can either renumber once into an RFC 1918 block and use NAT, or you can
renumber into a new space every time you change providers. Your customers
will understand renumbering once, especially if you can find a way to
improve services with it. They'll look elsewhere if it happens more than
once or twice, or if they get nothing from it.
Benefits of NAT? You can allocate as many addresses as you want to each of
your customers, regardless of how many you actually advertise. For
instance, if you had a provider with a cluster of servers, they could all
have the same external IP, and NAT could do load-balancing between them
internally (with a bit of hacking). I'm sure there are other benefits I'm
missing.
You can minimize the effects of renumbering by doing it at "off" hours, by
leaving old addresses active for a month, etc. There are plenty of people
who are willing to help you make this as painless as possible.
If Microsoft wrote noncompliant DNS code in their stacks, that is an issue
to be taken up with them, and something that can probably be incorporated
into the next service packs. This is not a NANOG issue or even a provider
contract issue. As for broken browsers, most applications cache the hostent
after the first gethostbyname() call each session. This is not likely to
change, and a 1 month compatibility period will easily be sufficient. After
all, have you ever seen Netscape run a month without crashing?