I agree with your point 100%, but if they're sorted you could probably just store the deltas an then use something like the varints that google protocol buffers to compress those deltas down from 32 bits (with a thousand of them, you are guaranteed that some of the deltas will be less than 22 bits because 1000 * 2^22 > 2^32).

With custom compression, where there's a will there's generally a way :)