Because of the fact that searches were slowing down the rest of the site, I have made the decision to run searches off a cached copy of the skins data. This cache will be updated every four hours. It's been running like this for most of the day today, and I'm really happy with the results. My goal is to keep the load on the server under 1.00 as much as possible, and to make non-search page loads under one second.
Thanks to a BlogSkins user who I can't track down right now for the suggestion.