They are more likely remanufactured device. Essentially it is a new phone with a new back and front glass, new frame, and new battery. Any working parts in the previous defected iphone are reused, and they do thoroughly test them to insure that they are working properly before given out as a replacement unit.
And no, the Genius usually picks up what's in stock, it can be 5.1 or it can be 5.0.1. They can't really tell which iOS version it is using inside the box unopened. If you are looking for a 5.0.1, then you have to hope that the replacement will be 5.0.1