So I was able to fix my code.
Indeed it seems that ProjectWorldLocationToScreen only works (and returns true) when the object is in front of the camera. Note that “in front of” includes the case that the object is off screen. When the object is behind the camera and inside the mirrored view-cone the projection to screen would result in on-screen-coordinates. Apparently the developers preferred to return false and no coordinates instead.
If that could be confirmed somehow, or documented even, I would be so happy.
My solution is this: When the projection fails, I manually calculate an object position in front of the camera and project that to the screen and then I translate the screen position to the corresponding edge of the screen.
This last step I was missing and it was confusing me to no ends.
And I still don’t understand the last parameter of ProjectWorldLocationToScreen. About ProjectWorldLocationToWidgetPosition I only see the more complicated code that make it seem less desirable performance-wise. I might try it out later, anyway.