I'll give it a shot, someone please correct me if I'm wrong.

Let's say we generate 10 trillion addresses per second, which corresponds to a few times more than 100,000 high-end ATI cards.

2^160 / 10 / 10^13 / 60 / 60 / 24 / 365 / 1000, or ~ 4.63x10²³ is the number of millennia it would take to generate nearly 1/10 of all possible addresses. "Nearly", because we disregarded collisions.

There are almost 2²⁵⁶ (2²⁵⁶-2³²-2⁹-2⁸-2⁷-2⁶-2⁴-1) valid private keys. Two private keys can correspond to the same address. So actually it would take ~ 3.67x10⁵² millennia to be absolutely sure you've generated 1/10 of all possible addresses.

If it's possible to check whether you have generated an address before, with zero cost, then you will know that you have generated 1/10 of all possible addresses some time between 4.63x10²³ and 3.67x10⁵² millenia. By comparison, the universe existed for about 1.4x10⁷ millennia.