I like the idea of using the stdint types. Since we don't have negative sequence numbers, we could use uint64_t to take the maximum from 9,223,372,036,854,775,807 (INT64_MAX) to 18,446,744,073,709,551,615 (UINT64_MAX).
The upper bound really controls how many job IDs can be active (queued, running, held, exiting, etc.) at any given time. This will always be something less than infinity, so I think having an upper bound is fine for our purposes.
Any decimal number beyond about ten digits starts getting a little intimidating for us puny humans. Even with hexidecimal we're looking at a string of 16 hex digits to represent UINT64_MAX. That's a little better than 20, but not much. Even with hexatridecimal (base 36) it's still 13 characters, with the possibility of some vulgar words embedded.