Check your settings against this article:
BlackBerry Search Results
If everything checks out then post the errors you are receiving. You only need to restart the Alert service, the Router is only for the Send As issue.
Also, you don't have to use the BESAdmin account either, you could use any account you want to receive the alerts.
Keep us posted.