During the boot the phone by default sends out an HTTP request to http://provisioning.snom.com in order to check the redirection service.
In case your phone is in a closed network this request will fail and the phone will show the provisioning failed message.
Moreover if your firewall is just dropping the connections instead of rejecting the phone will wait for the TCP timeout, this can make the boot process longer than needed.
You can skip the provisioning requests to provisioning.snom.com configuring properly the setting provisioning_order: removing the "redirection" keyword the phone will not even try to contact the redirection server. In order to accomplish that you have to change the value to: pnp:stop tr69:stop.
You can do it trough provisioning or via single HTTP request:
http://phone_ip/settings.htm?settings=save&provisioning_order=pnp:stop dhcp:stop tr69:stop