Intuitively: Every seven years. Remembering leap years: In 28 years, tops.

Thinking about it: Has to be more often than that; there are only seven weekdays the year can begin on.

This is only considering getting the weekday for every date right; moon-phase stuff like the date of Easter will make it (much?) more rarely.

OK, will go read the article now...