Posting to both org-mode and gnus groups.
Just updated to latest org (9.3 of 3 December) on Emacs 26.3.1
and my gnus link functions seem to have quit.
Now, whenever I do C-c C-o on an email link I get something like this:
org-link-search: No match for fuzzy _expression_: gnus:nnimap+imap.gmail.com:%5BGmail%5D/All%20Mail#CAN9LUGf6QKkyxt9EWJJs+hOYC6yWJASFT4K4hV5Zr2D10VyJWA@mail.gmail.com
Very strange! Just an hour back, my test suite failed because earlier org-link-unescape used to unhex but now it doesn't. I haven't yet traced back to the commit where this change happened.
Then replacing org-link-unescape with url-unhex-string fixed my use case.
Not sure if the issue you are seeing is because of the same cause.