We once had a bug that would cause a failure in our test suite, but very rarely. It was so rare that it would just "go away" and not show up for weeks. So we thought it was odd (maybe bad test data, etc) but moved on. When we decided to look into it when we had some downtime, we found out that it was a date bug that only reared its head on the 31st day of the month, hence only happening every two months. I'm not sure…
Thanks for the anecdote, because it gives me a new idea. We should be monitoring the rate of test failures -- per test -- in a timeseries and looking for periodicities. Just graphing them and seeing regular spikes will help, but having real numerics looking for approximate periodicities will catch this sort of thing (after a few months!).
But, as a general rule, I would try to brute force or fuzz your "inputs", a.k.a data out of your control. Random numbers, dates, user input, network packets, etc. Users and environments often act in unexpected ways and you want to make sure your bug finding isn't reduced to accidentally be working on the right day! :)