No, our firewall is Fortinet.
To reiterate - the same browser instance on the same machine CAN access spark.co.nz if we change the source public IP address and simply refresh the window - no other changes are necessary to get the site to work. We have tested different machines running different operating systems and different browsers (using inPrivate and portable versions) to rule out other possibilities - keeps coming back to the public IP address (or something beyond our vision anyway)
This is why we believe it to be something not liking our public IP (but no clue as to what/where that might be)
You keep saying public IP. Is the Fortinet appliance in all IPs you tested?
When you change the IP are you changing networks or network providers?