I have heard some do and others do not.
I think they would not really be an Arduino of any kind if they do not. But that is not going to stop them on Ebay.
Yes they do (unless the seller/factory forgot to program them, which is always possible of course).
I've brought in quite a lot of them (some for use, some for resale), and never, touch wood, had a bad one. Although I don't buy them from ebay.
Just watch that they have a 328 on them, I've seen them being sold with the 168.
Of course if you were unlucky to get one without a bootloader, you'll just need a second working one to act as ISP to load the bootloader on the dud.