The estimate wasn't too high, it was too low. I had to up by 50% to 3 Mil to make sure it got through and it cost 2.6.

If the gas paid isn't enough it should be returned to you, Eth network stealing the users money for work it didn't complete isn't good enough. IMO this is a perfect illustration of why nothing serious will ever take place on the Ethereum network. People don't want to pay every time they interact with the blockchain, companies don't want to pay every time they interact with the blockchain ... even if you do have to pay, you at least want to get what you paid for (or have the funds returned to you). Smart contracts are supposed to prevent this sort of thing happening, not be the cause of them.