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
select * from records where startdate < "2014-01-30 00:00:00" and enddate > "2014-01-01 00:00:00";
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.