Being able to perform wildcard search is probably an area that's missing in out of the box search in SharePoint. Here's a small web part sample you can use to perform wildcard search in MOSS 2007 (and it can be engineered backward to fit into SharePoint Portal Server 2003 as well).
The code in it is very crude, I agree :) It's just a sample I wrote once and built upon multiple times for several different customer situations and so you might find commented out code snippets. I have not put in any comments to explain what I am doing - sorry about that. But I believe, a good developer's eye would catch-up on those code details very easily.
My other reasoning is: If it was so difficult for me to pull this code up, it should be that way for people who read this code :) (A traditional developer-related PJ I read somewhere...).
Nevertheless, try using the sample web part (oh yep, you need to have the latest WSS 3.0 Tools: Visual Studio 2005 Extensions, Version 1.1 installed to be able to open the enclosed VS solution) and let me know how it is.
Hopefully, it helps you as it helped many of my customers!!