Did some more testing...
This is implementation issue in the photostream. It is expecting that if wifi works then connection to the server works, too. Obviously it start trying, when wifi connection is present. However, if it the server connection fails, then it drops everything and those photos being "streamed" will never stream again.
I have three iCloud devices, and only one can be connected to photostream at a time, due to limitation in my VPN account (needed in China). It means that I have not only one stream but three dysfunctional streams.
I would had expected that new photos goes to photostream "cache" or "queue" or what-ever in a device and when connection works end-to-end it uploads the photos to the stream and from the stream. Current way is a bug.*