It seems I am on the same boat, not sure when this happened on my instance but I must assume with the latest or one of the latest update.
The contacts show up in NC Mail as well as in the Search, but I cannot open them from there
Perhaps someone can merge the two threads ?!