Found the problem and solution,
The plural string (second parameter of _n()) doesn’t expect the same notation in the .po file, but a plural specific one.
Changing:
msgid "%s message"
msgstr "%s bericht"
msgid "%s messages"
msgstr "%s berichten"
to this:
msgid "%s message"
msgid_plural "%s messages"
msgstr[0] "%s bericht"
msgstr[1] "%s berichten"
Worked