What search are you using? Works for me in standard Special:Search with quotes and spaces.[1] In general, if you have the exact message id it's easier to just visit the title in question, with MediaWiki:<id>/en.