Having just gone through selling a car, I can tell you that CarMax will most likely not be the best solution. I recently sold my '09 Pontiac Vibe which had a KBB and Edmonds value (private party sale) of around $6k. Trade-in value was around $4,800. I took it to the local CarMax for a quote, and they came back with $3,500.
Refinancing is tricky. Banks have a set limit on how old a car they will finance. Many won't even offer financing if the vehicle has over 100k miles. We looked at refinancing our other car, and even getting the APR down over a point we would only have saved $15/mo or so. Banks typically offer much higher interest rates for used non-dealership cars and refinancing than they do for new cars, or even used cars purchased from a dealership. Assuming you have 2-3 years left on your loan, I don't think that refinancing would save you enough to be worth considering.
CarMax sells cars in 1 of 2 ways. They are also up front with you about the process. They do not reference KBB or Edmonds or any other valuation tool other than their own internal system. They either take the car, spruce it up a bit, then resell it on their lot, or they sell it at auction. If they determine your car will be sold at auction, then they will offer you a rock bottom price. The determining factors that come into play include age of the car, mileage, and of course overall condition. If you Mini is still in good shape and doesn't have a lot of miles, then they may try to resell it on their lot, for which they could offer you closer to personal-sale price than trade-in. How many 2007's are for sale in your area? How much are they selling for? I did sell them a truck back in 2005 and received $200 more than KBB valued it for, but it was in great shape, only a couple of years old, relatively low mileage, and it was in high demand. God bless the South and their love for trucks!
I ended up selling my Pontiac to another local car dealership. They offered me $5,300 (after negotiating, leaving the dealership, then negotiating more over the phone). It took me a day and a half and really very little effort. I have several friends that have gone through the same thing with selling cars, and all have had similar luck going to other dealerships, where prices can be negotiated, rather than CarMax.
CarMax has no incentive to "settle" or forgive your loan. If you really want to pay it off, save up what you believe the difference will be, then shop your car around the local dealerships and get prices for your Mini. Remember that dealers have to turn a profit, so be reasonable with your negotiation. If you can find comparable vehicles in your area listed for $X,000 then knock $1,500 off that price and tell the dealerships that's what you want.