If we do option B, and do a url rewrite server side before the page loads so there will be no duplicate content because the original non-variable link will no longer be available, will that affect SEO?
If you internally "rewrite" the URL, then the user/google will still see the URL with ?mi= parameter, this will create duplicate content.
So if we redirect all existing pages to add the parameter and tell WMT to ignore "mi" because it doesn't change content,...
How are you going to "redirect" existing page to add the parameter? Redirect would mean that the page arrives without the parameter, and then you would issue 301 redirect to a page with the parameter - and this would be no good.
There is another option you might want to explore, for this I am assuming that you would have internal link somewhere with the miles of the closest store (I am quite not understanding whether your distance information is a distance between city centre and the merchant or distance between user and the merchant and if it is from the user, where do you get the information on miles distance from the user, i.e. how do you figure out what should be your ?mi= parameter).
But assuming that your original idea was that you intended that the URL with ?mi= parameter was an internal link somewhere on your site, and that the URL with and without mi= parameter would return the same page content, then you may want to explore Google Analytics Event Tracking code instead of using ?mi= parameter.
This is tracking that you can set up within your GA, and then ensure that you put the correct syntax in your HTML source. The syntax would be something like:
<a onclick="_gaq.push(['_trackEvent', 'miles-distance', 'clicked-on-link', 'Pet store in Boston', '9 miles']);" href="/pet-stores-in-boston-ma">some anchor text</a>
This would work only for internal links though. Search for "Google Event Tracking" for more.
<added> The above is just an example, you would have to figure out how to best set up variables and what to track where to get what you want. </added>