It is quite thrifty with memory compared to the size of the search space O(n*k) memory for a search space of size O(n**k).

I think a reasonable expectation for itertools.product is that it should _eventually_ reach any element in the search space. The only way to maintain that expectation for infinite iterators would be be to use a Cantor-style zig-zag enumeration. Even for your example of searching over a single infinite iterator, you could end up exploring dates in the order (2010, 0), (2011, 0), (2012, 0), ... by switching the ordering of inputs. You'd never hit the rare date unless it happened on the first day of a year. 

There's no way to have special behavior _only_ for infinite iterators, since an infinite iterator is indistinguishable from a long-finite one due to the halting problem, so this would require changing the behavior for finite iterators too. While the output ordering is not explicitly documented, the current search order is probably depended on by plenty of existing programs, and has less surprise than a Cantor enumeration.

So the only use case where the lazy enumeration matters is if:
1. You have one or more _very_ large iterators.
2. You _do not care_ what order they are searched in, or even if all possible tuples appear in the output.
3. Despite not caring about the output ordering, you still only want a few examples.

I'm struggling to think of cases where that would come up.