Mosquitto allows my devices to connect, but will publish/sub messages once per 3-8 connections

Hello! I have a very strange problem with MQTT broker on HA! It works great internally with Z2M etc, but I have strange issue when I try to connect to it via:

→ Node Red
→ Arduino Mega with PubSubClient and W5500 Lan module to connect with HA via MQTT via LAN.

Symptoms - the connection is estabilished properly, clients are connected but everything they publish or subscribe to is not delivered or received, they are like “dead”. Once every 1-8 reconnections the connection is estabilished as should and everything works.

Case:
I just simply publish two messages at the start of the Arduino program, receive them in HA and do actions based on that. On the bottom half of the screenshot you can see a proper connection made - it starts with “MQTT connected” and sends and receives 2 messages just at the beginning of a program.

If I am lucky and the connection is estabilished the proper way it will stay okay. But when I restart the Arduino (Node Red too) I have to make 2-8 restarts (the number is random) to get that proper connection with working messages, which you can see on the upper section of Serial Monitor I had to do 7 “connections” which ended in no message send.

The same is with node red “MQTT IN” node with subscription to “#” topic - it will work once every few restarts.

I have tested my Arduino MQTT with test.mosquitto.org and MQTT Explorer and my setup works everytime as it should - sends messages in 100% restarts. Tried that on two different boards with two different LAN modules. So I think I have narrowed the problem down to something with Mosquito Broker in HA maybe?

Would be glad for any input and help, very random connection problems with a fixed amount of restarts needed to work (3-8) okay are always strange in IT world and I am really tired of that - this makes my automations epic unreliable.