I need a away to effectively search substrings.

The situation: I have a claim number field (consider it to be a random alphanumeric string). My user base was trained that since the claim number field could take wildcards, it's best to put them both before and after your search term, which effectively prevents any use of SQL Server indexes. The trainer needs to be introduced to the ballbat of doom. Now we can't fix the functionality to not allow the extra wildcards because that'd mean changing all of our trained user habits, and in addition our "project manager" (who is actually a client advocate, not a project manager) is simultaneously complaining about slow performance and exclaiming that the ability to do this type of search is absolutely critical.

Since the claim number is random alphanumerics, Microsoft Search Service interprets it all as noise, and won't index any of the values in the table. I've tried editing the noise word files, to no avail. All of the noise word files, for every language, on each server instance, and the ones in \windows\system and \program files\common files\data\microsoft search. While it will probably work in SQL Server 2005, it doesn't work in 2000.

Thoughts?