If leaking creation time is a concern, can we not just fake the timestamp? We can do so in a way that most performance benefits remain - so like starting with a base time of 1970 and then adding base time to it intermittently, having random months and days to new records (or maybe based on the user's id - so the user's record are temporally consistent but they aren't with other user records).

I'm sure there might be a middle ground where most of the performance gains remain but the deanonymizing risk is greatly reduced.

Edit: encrypting the value in transit seems a simpler solution really