There is no way of knowing for sure.
My guess is that they do get recycled eventually after being redeemed. I am guessing Microsoft keeps some kind of "pool" of unused keys to use for new things. Once a one-time-use key is redeemed, I am guessing that Microsoft will put it back into the pool.
It is true that keys may be left in boxes or on store shelves for a very long time or even for forever. This means that they can't just use them as they please and they can't just randomly generate ones when they need new ones because they may already be out in the wild.
That all being said, the format they use for their keys is a 25 character, alphanumeric string. This provides enough uniqueness that they could probably get away with using news ones forever. At least in a given region. They may re-use keys between North America and other regions for all we know, the games don't work the same, I wouldn't expect the keys to either.
Bottom line, your guess is as good as mine.