>How about not storing any information at all? Nothing to give, problem solved.

This means no history sync, no seamless device switching, no contact discovery, no search. That's not what people want.