I solved it myself, just a while after asking this strangely.
The answer is simple: You need to set NOTIFYICONDATA::szInfoTitle
to something. In my case, I completely forgot about it, and expected it to use some sort of default title, but it didn't. Instead, it got replaced by garbage, making it unreadable.
To solve it, I added:
StringCchCopy(s_data.szInfoTitle, ARRAYSIZE(s_data.szInfoTitle), L"Test title");
And now everything appear neatly.