Ok... I'm confused. There are two ways to do search:
1) a real-time live search (i.e. Google, Internet Explorer, etc)
2) only do the search when the user clicks the OK / search button
For #1, you would do it on every key stroke.
For #2, it depends on how your UI is laid out. Do you have a pop up dialog with an OK button? Or is it something like where you have an edit box in the main window frame?
Irregardless of how you are implementing #2 UI wise, I think you are confusing your property setter with your action trigger. Those should be separate. The "public string SearchText" property should not kick off a search. Since all you should be doing in it is updating the property, its fine to update it 50 times. Then your enter key / ok / search button will send a command to the VM to kick off the search.
The button sending the command portion I'm assuming you already know how to do, for trapping the enter key, all you need to do is use your EventToCommand mapper to map the KeyDown event of the edit box to an ICommand and forward along the eventArgs. In your command handler function, you would simply check if the key pressed was the enter key. All nice and MVVM'y .