I've hit the same sort of problem with an integration project. I wish there was a good solution...
You cannot create an index for a property that is not already indexed by Exchange. Creating a search folder for each is not viable if the number of Appointments grows high enough. Too many search folders on a single folder will cause further problems as they will all need to be updated when a new item is added to the folder. That's my understanding, at least. Also, Exchange 2007 is limited to 11 dynamic search folders per parent folder, so it may be even less viable depending on the number of appointments and how often they're accessed. Using existing indexed properties may not be viable as these can likely be changed by the user outside of your application. If you have some way of ensuring that the Appointments you create can only be accessed or altered from your application, then that's a different story.
The database table is a good way to go, but there's a potential snag that some people don't see until it's too late. ItemId is the obvious choice to link to your extended property, but ItemId is NOT constant. It's a calculated property based on several others. It can change if the item is moved to another folder, and it may also change with the installation of a service pack or given enough time passing, or so I've heard. I can confirm at the least the first one. ItemId is not viable for long-term storage, at least not without additional checks. You could potentially store ItemId and your extended property. If a bind using the ItemId fails, fall back to the extended property search. If the bind is successful, then check it against the extended property in the database to be certain that it matches. Update the ItemId once you have the item if it doesn't match up. Do you need to work with anything beyond the Appointment objects, ie, meeting responses, forward notifications, etc, or is this concerned only with the Calendar?
It isn't pretty, but it should be a somewhat reasonable compromise. You may still have the occasional search, but they should be few and far between as long as the user doesn't decide to move Appointments to different folders or plans some Appointments way in advance, and even then the sync should help mitigate that as well. Just be prepared to repopulate that table if there are upgrades to Exchange.
Of course, if Microsoft had either added the capability to index additional properties or even added a blank string field or two to the index in Exchange Search for this very purpose, we wouldn't have this problem. Heck, an index on the GlobalObjectId properties on Appointments and associated objects would help, but alas...no. I'm not a fan of repurposing existing indexed fields. Not all of them are applicable to Appointments and the ones that are tend to be either required or editable by the user. Unless you know precisely what you're doing, repurposing those fields could potentially have unforeseen consequences down the road.
In any case, I don't claim to be an expert in all matters of EWS/Exchange, so maybe there is a better way than this. Take it with a grain of salt.