[xyzzyz]

Its expected value will likely still be linear - since values are distributed among cells uniformly, and there ratio of empty cells to all cells is bounded from above (otherwise rebucketting occurs), expected position of the first nonempty cell is also close to the beginning. Calculating it is a good exercise, helpful Google keywords are "order statistics of discrete uniform distribution".

[alexbecker]

No, because you're erasing the cells in order. So the first nonempty cell will get progressively further from the beginning.