A while back, Kyle Baley of CodeBetter.com wrote an article named "The search interface, or "How to find people"" where he discussed the vast array of interesting questions that come up when considering how to make your search results as relevant and useful as possible.
When he mentioned that his database did not support LIKE, I offered another method within Kyle's comment board. However I had a bit more of detail I wanted to go into, but didn't have the time to expound then.
Basically, I think many of Kyle's ideas are spot on, however, the best result may be to simply code a number of queries in, and provide them as fall-back options. Here's an example in PHP, my preferred language, especially for examples:
$query = $_REQUEST['query'];
$max_results = 10;
$results = array();
$queries = array(
"SELECT * FROM contacts WHERE last_name = '?'",
"SELECT * FROM contacts WHERE LEFT(last_name, ".strlen($query).") = '?'",
"SELECT * FROM contacts WHERE first_name = '?'",
"SELECT * FROM contacts WHERE LEFT(first_name, ".strlen($query).") = '?'",
foreach($queries as $sql)
$results = array_merge($results, fetch_all($sql, $query));
if (count($results) > $max_results)
This way, you can return the ones you feel would be most relevant first, but then make sure you can provide for some of the edge cases as well.