I had the same problem (and, really, 5 years?), but "solved" it at the time with ISO8601 strings. They sort, they're standard, they support microseconds, they're fairly common in web services. Slower than a reasonable native type though, obviously.