I like the leap-hour once every 500 years or so idea.
But I suspect in practice, it would never be actually assessed. When it comes due, everyone alive would be more accustomed to the 'hour off' times than the 500-years-ago time, so natural tendencies to eschew change in such matters would make following-through on the promised leap-hour unlikely.