The core Drupal search module uses several template files that dictate both how search results are displayed, and what's displayed when there are no search results.
If you're already using a custom theme on your Drupal site, the best way to customize those would be to copy and paste the entire 'search-results.tpl.php' file from the search/ module folder into your own custom theme subfolder.
Open that file up for editing and you'll see the following 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; ?>
This is what's displayed if search results are not found (thus the 'else')... Modify the text to be anything you want here. The second line, which calls the search_help() function is the one that displays the search suggestions. Feel free to replace that too....
And as always, before you can see your changes, you'll probably need to clear cache!
Let us know if this works for you!