Ok, answer was given in MS forums:
Manually add index: Go to library settings > Indexed columns > Manually add the lookup column, then
Go to Site settings > site information > view all site settings > Search and Offline Availability > Reindex the site.
After reindexing (which can take some time, depending on volume) search works.