Figured out the reason of a such error.
In my case looks like a bug in Windows.

In short: contents of the icon doesn't matter*. The problem is in modified %TEMP%

As you perhaps know(?), if you include your own icon file as a form's "Icon" property, VB runtime calls OleLoadPictureEx() which then firstly write icon on disk in the TEMP folder returned by GetTempPathW().
So, if system has no access to that folder (e.g. missing or permissions issue), or has incorrect %TEMP% environment variable or so, you'll receive "Invalid picture" on app start. Sometimes I saw altered record in the registry - instead of REG_EXPAND_SZ, "Temp" value have a type of REG_SZ preventing the data "%USERPROFILE%\AppData\Local\Temp" from normal expanding.

Well, why I called it a bug. In my case, the problem was deeper.
There is a weird behaviour in Windows where it can assign custom TEMP value overriding current variable by volatile environment variable when you connect to machine via RDP session. So, the final %TEMP% will look like this: %USERPROFILE%\AppData\Local\Temp\2
where the folder "Temp\2" does not exist and does not create automatically by Windows.

Behaviour may be disabled by GPO, as described here.

So, there is a solution: check does %TEMP% exist and accessible.
As automatic solution:
1. You may not use form's "Icon" property at all and load icon manually (by code).
Or
2. You may start app from Main() or load from hidden form having no icon, then check if %TEMP% folder exists (and accessible for write access), if no, create it or modify %TEMP% to point to the correct location. Then, you may safely load other forms having custom ico file in its "Icon" form's property.

*well, there is surely some rules about icon creation, like the presence of 24bit images (of some sizes - sorry, don't remember exactly) which is essential for some unpatched XP.
Here is a minimal set what always worked for me in all OS versions:
32x32 (24 bit)
16x16 (24 bit)
48x48 (32 bit)
32x32 (32 bit)
16x16 (32 bit)
+ 256x256 (32 bit), this one is inserted by patching the exe file (required for good look only).