(1) Bob is optimizing long-term savings, and Joe is optimizing purchasing power for nearby activities like bars and restaurants. After subtracting other comparable expenses, any salary surplus strategy which is a "perfect" cross-city CoL adjustment for Bob will when applied to Joe cause him to prefer a cheaper CoL location because his dollars will go further. Supposing the employer doesn't have power to discriminate based on such preferences, no fair CoL adjustment is perfect for both individuals.

(2) Bob is still optimizing long-term savings. MegaCorp chose a "perfect" CoL adjustment based on Bob's preferred standard of living, but the multiplicative nature of price increases in a high CoL city means that Bob can save a ton of money with a mild decrease in his standard of living. He's incentivized to live somewhere more expensive because doing so will maximize his potential savings with minimal impact elsewhere in his life. If the employer isn't discriminating based on what's paid for rent and other expenses, the CoL adjustment is gameable.

It's much easier to move from an expensive city to an inexpensive city than vice versa since your savings will go much further in the inexpensive city.