We've always assumed that non-shift movement was safe, as long as it was movement between squares adjacent to the enemy. The way we've played it, only movement from an adjacent square to a non-adjacent square provoked OA.
(I have no idea how this misconception has managed to survive for this long. Reading the compendium entry and the Player's Handbook, the rules are perfectly clear and even simpler and more logical that what we've been doing.)
My question is, should I correct the group, or should we keep playing the way we've done?
Apart from just having to adjust to this mechanic, combat is probably going to change somewhat. Flanking will become harder to achieve (something we've always taken for granted - two of the players even got the Eyes in the Back of Your Head feat to avoid getting flanked), safe movement will be more expensive, shifting more valuable and threatening reach a lot more threatening - melee characters won't even be able to attack it without provoking OAs (actually, I've always wondered why there weren't more monsters with this property).