Wow, that's backwards, but I certainly understand why you are doing it that way. It makes it much harder, though. If you were to do it like this:

0000 through 0009, then 000A, 000B, etc.

that would be relatively easy, because you are effectively using a base-36 number with digits 0-9, A-Z. Otherwise, the sequence is like any other number. However, you are using a base-10 until you have reached 1000, then the most significant digit becomes base 36, and so forth.

I guess the first question is whether or not the order of those numbers justifies the pain of the implementation?

Assuming that you don't have any flexibility, this is a very clear case where you need a class (all it AlphaNumber) with a method called GetNext, because there's going to be a bunch of housekeeping involved figuring out what the next number is. I'd also have a base-36 class that would return the next value in base-36 (you don't need a base-10 class, because that one's too easy). I'd then have the AlphaNumber class maintain an integer counter variable and a base-36. There would also have to be a variable to keep track of where the base-10 integer rolls into the base-36 number. It would look interesting, but before I go any further, decide whether or not you really need the numbering system to work that way.