In the end it was in fact two problems. The 4.7.1 was due to greylisting behaviour which you helped me with, thank you. This explains Scenario 2 in my first post.
But also, one of my inbound MX IP was getting banned by fail2ban I found so I had to whitelist that IP which explained Scenario 1. Other MX IP we not banned, I am not sure why this was happening but everything is back to normal now.