It seems to me that your problem is in your first sentence:

> Our company implemented a calendar system a few months back with recurring appointments, *using iCal strings to store the recurring appointment criteria*.

Having to scan all records to determine date ranges is simply not scalable.  In essence, you're using your database as a flat file, so of course it is slow.

Instead of storing the raw iCal strings, interpret the strings *before* you put them in the database so that you can run queries like

<!-- language: lang-sql -->

    select * from records 
    where startdate < "2014-01-30 00:00:00" and enddate > "2014-01-01 00:00:00";

If you really need the iCal string, you can leave that in the DB as well, but things like appointment start/end dates should be db columns so you can efficiently search on them.