detecting recurring appointment conflicts

I'd like to store recurring appointments in my database, and be pretty
accepting in the scheduling of those appointments. For instance, I
want to accept both "every other Tuesday starting 2008-11-04" as well
as "every 3rd October 13th starting 2009." Storing those appointments
isn't that hard, but what isn't at all obvious to me (and what I'm
hoping is obvious to somebody else) is how to efficiently detect if
and when overlaps will occur.

I can see a few ways to look for schedule overlaps in a defined
window, but ideally, I'd like to know if there will be overlaps at any
time, not just in, say, the next 10 years. (Though, admittedly, the
next 10 years is probably sufficient.) Is this something somebody has
tackled before?