Your question inspired me to finish adding this feature to one of my plugins (Sublime 3 only), since this also bugs me.
sublime.wbond.net/packages/Column%20Select
The issue is that it seems Sublime combines all successive motions into one, even with soft undo. This plugin is a little bit of a hack solution to remember which direction you were going, and undo the last movement if you go the other direction. So if you CTRL+ALT+UP one too many, just press CTRL+ALT+DOWN.
This plugin does a few other things (like adding mouse support, pgup/pgdn/home/end, making begging/end of lines sticky, ignoring lines that are too short). If these other features are in your way, if you know a little Python it should be easy for you to rip out what you don’t want. Or even better, feel free to send me suggestions.