I faced the same problem with an integration project. I wish there was a good solution ...
You cannot create an index for a property that has not yet been indexed by Exchange. Creating a search folder for each of them is not viable if the number of destinations grows high enough. Too many search folders in the same folder will cause additional problems, since they all need to be updated when a new item is added to the folder. This is my understanding, at least. In addition, Exchange 2007 is limited to 11 dynamic search folders per parent folder, so it may be even less viable depending on the number of destinations and how often they are available. Using existing indexed properties may not be practical because they can be modified by the user outside of your application. If you have a way to make sure that the meetings you created can only be accessed or modified from your application, then this is a different story.
A database table is a good way, but there is a potential error that some people donโt see until it is too late. ItemId is the obvious choice to reference your extended property, but ItemId is not a constant. This is a calculated property based on several others. It can change if the item is moved to another folder, and it can also change with the installation of the service pack or with enough time, or I heard it. I can confirm at least the first one. ItemId is not viable for long-term storage, at least without additional checks. You can potentially store the ItemId and your extended property. If the binding using ItemId fails, return to the advanced property search. If the binding is successful, check for an extended property in the database to make sure it matches. Update ItemId if you have an item if it does not match. Do you need to work with anything outside the Appointment objects, that is, respond with answers, forward notifications, etc., Or is it just the calendar?
This is ugly, but it should be a somewhat reasonable compromise. You can still have a random search, but they should be few and far apart until the user decides to move the assignments to different folders or plans some appointments in advance, and even then synchronization should help mitigate this, just be prepared to re-fill this table if there are updates for Exchange.
Of course, if Microsoft either added the ability to index additional properties, or even added an empty string field or two to the index in Exchange Search for this purpose, we would not have this problem. Heck, the GlobalObjectId property index in Assignments and related objects would help, but alas ... no. I'm not a fan of repurposing existing indexed fields. Not all of them apply to Assignments and to those that are usually either required or edited by the user. If you donโt know exactly what you are doing, reprofiling these fields could potentially have unforeseen consequences in the future.
In any case, I do not pretend to be an expert on all issues of EWS / Exchange, so there may be a better way than this. Take it with salt.