- Using specific metadata - While this may not suit your purpose, but you can search for somebody's firstname by, Firstname:Rob, this will give you all the people whose names are Rob, Robe, Robbie Robbin etc. (You get the idea) Similarly you can search for lastname too. Please note that if you try searching for Robbie using FirstName:bbie, you will NOT get the result.
- Customizing the search result web part - Mario Hadiwinata lists down a method of doing it. I have not tried it myself, but it looks pretty sleek. [Edit - this works for sps 2003 only and not for MOSS. Thanks sdec for pointing that out]
- Using a CEWP webpart - Ramon Scott lists down the code to use it on your homepage. This creates a new webpart with two text boxes, where you can do a wildcard search on people by lastname or firstname.
- Use Ontolica Wildcard Search - This is a free download provided by Ontolica here.
Other than these, there must be various solutions out there, but on the similar lines.