Ok seems that there was an issue with the time set on the server. I noticed that email entries in DB were 2h behind current time as they were created. I check the system time settings and noticed it was not set currently. After I set correct time on the system the emails have started going out. Tho it is still not touching the old emails still in queue.
Will be doing some more tests in the mean time. Is there a system in place to clear email queue or can I just delete all failed entries from DB without consequence?