The easiest thing for you to do would be to override the actual template file which displays that language.
Look at the template file called search-results.tpl.php in the core search module.
It has the following code at the bottom:
<?php else : ?>
<h2><?php print t('Your search yielded no results');?></h2>
<?php print search_help('search#noresults', drupal_help_arg()); ?>
<?php endif; ?>
Copy the entire template file (you don't even need to rename it, it'll override the file in the module) and paste it into your own theme's /templates folder. Re-write the section I've pasted at the top to be whatever you want. The part that prints the search_help() is the bulleted list you're looking to change.
Of course, before the system will pick up your new template file, you need to clear all your caches!
Let us know if this works!