Maybe add a second enumeration for the sorting and make sure the values are set with a batch job (can be a microflow, depending on the amount of records we're talking about else do it with java (as you are on 3.3.1). Make sure for new records the second enumeration is set and sort on the second enumeration. This is still sort of a conversion only you're not touching the existing data.
I've thought about the option to create a second enumeration as well, but it is still a work around.
I'll file a feature request to be able to define the sort order for enumerations without naming the keys.
Update: I've submitted a feature request to be able to influence the sorting of an enumeration independent from the keys. This feature request has been turned into a bug report by Mendix, and is now nominated for release.