Search: Present a user friendly message with invalid regex

Fixes #1821