the error message is just "banned IP"?
Did you check, if the IP is black listed for any reason? http://mxtoolbox.com/blacklists.aspx (or any other service to check black listed IPs)?
So it all started working yesterday afternoon, having changed nothing else on our side. I can only assume that the IP un-banning takes a lot longer than the 30 minutes suggested.
It will be interesting to see whether it is still working on Monday.