Good point, Petr - but making the auto-create groups system add leading zeroes doesn't seem like the "nicest" (from a user's perspective) way to fix it, especially if you have 100+ groups - and it won't affect existing groups.
Perhaps what we need to do is simply add a new (numeric) column which gets populated automatically by the auto-create groups system, and sort by that first and the group name second? It could be exposed as an advanced option in the group also, so that the sort order of manually-created groups can be tweaked if necessary. The field could be left null (or set to 0, to achieve more consistent results on different DMBSes - I think some may sort nulls before all else and others after all else) for manually-created groups without sort orders specified, and the auto-create system could then grab the maximum sort for groups in the relevant context and start at the next index.
While this approach wouldn't necessarily result in all groups being sorted (auto-created groups would be in one block after all manual groups with no explicit sort order set), it would resolve the issue for auto-created groups, which are the primary issue. It also would not break any 3rd-party blocks/modules which list groups, since they'd just continue to sort in the existing manner if not updated. Groupings could simply have an advanced setting for sort order - that might be nice to add either way, to give a little more control.
Alternatively, the auto-create system could be tweaked to use two columns - a (string) "prefix" stored in the existing group name column, and an integer index stored in a separate column for groups auto-created using the "#" placeholder (those using "@" for letters could still be stored as the group name only). Groups could then be sorted by name followed by index. It does, however, mean that the check for group name uniqueness would need to be modified to check the suffix as well as the name, since you'd end up with several groups with the same name but unique indexes. The # denoting the position of the number within the group name could remain in the database, so the number goes into the correct spot.
This approach does require post-processing of the results in order to replace the placeholders, which may cause some performance degradation, though, and will require changes anywhere that groups are fetched/listed (preferably to use a library function to fetch groups which handles this). Such a change would probably be best done in 2.0 only, since it could easily break existing functionality in 3rd-party blocks/modules (they'd end up showing a bunch of "Group #" items).