I found the problem (with the help of another answer). The files 'grep' did not show any output for were not actually utf-8 encoded, but utf-16be. I learned this using hexdump (credits to @RedGrittyBrick):
hd file_for_which_grep_works_as_expected.txt
yielded
00000000 20 20 20 20 50 61 74 74 65 72 6e 0a | Pattern.|
0000000c
whereas
hd file_for_which_grep_fails.txt
returned
00000000 fe ff 00 50 00 61 00 74 00 74 00 65 00 72 00 6e |...P.a.t.t.e.r.n|
00000010 00 0a |..|
00000012
So, double-checking the encoding with
file -i file_for_which_grep_fails.txt
identified it as text/plain; charset=utf-16be.
I failed to recognize that the utf-8 shown by vim were actually the buffer encoding, not the file encoding. Executing :set fileencoding in vim also correctly displayed fileencoding=utf-16 (found here https://superuser.com/a/28783/1210682).
So, the problem is that my grep does not work on utf-16 encoded files. This has already been described here: https://superuser.com/a/231471/1210682. However, the remedy of converting utf-16 files to utf-8 before grep does not work when I use it recursively, as I don't know beforehand which files may be utf-8 and which utf-16 and a am searching through a lot of files.
There are different solutions, two of which I am going to shortly describe here:
A quick-and-dirty solution that worked for me was to expand the search pattern to include one that would match the utf-16 version and search for one of both patterns:
grep -riPa . -e "pattern|p.a.t.t.e.r.n."
This is of course very limited in terms of possible patterns.
There are alternatives to grep like ugrep or ripgrep that (among other things) can handle utf-16 files. I ended up using ripgrep which is available in the standard Ubuntu package repositories from 18.04 on:
rg -i "pattern"
There is a great discussion on alternatives here: https://stackoverflow.com/questions/3752913/grepping-binary-files-and-utf16, among them an interesting approach attempting to convert the search pattern to utf-16 and feeding that to grep. However, I couldn't get it to work.