You phone already stores lots of data every 10minutes, I am not sure if flash wear is a problem. Same with storage space.

A guid is 16 bytes per key * 6 keys per hour 24 hours per day 365 days makes less than a megabyte. Even accounting for additional data stored where guid is the key it feels not a big concern.

I imagine data stored like: Key: guid Contacts made: <timestamp, guid>[]