They do, I read somewhere that out of 35 million addresses in the system, only 24 million are verified. Still, I imagine that there would be false positives in the verified emails list (for instance someone clicked on it by accident or without reading it as they were signing up for something else, etc).