I haven't actually spent ANY time onsite yet between leaving it to the experts and being away a bit. - The Voip guys have and they assure me they have tried another router and the problem remained.
On Monday I'm heading there - I've prepared dyndns and dropped the TTL's and one thing we will try is removing the static IP with Spark to see if the problem goes away - Then it still could be a spark problem or could be that the IP is blacklisted or something at 2talk (Although apparently thats been checked).
While I'm there I'm going to try a SIP softphone and see if that works first on the Fibre and then to confirm secondly on the 4G.
We are also going to change the subnet of the 4G as currently one other "difference" that has existed in the various testing is that the Avaya has two NIC's and we have had the 4G on the second NIC so we are going to rule out an issue with the primary nic - Would be a strange fault if it was one and again no config has changed. Likewise that'll test if there is an issue on the LAN on that side of the network - Pretty unlikely again as all other traffic to the Avaya is fine from SIP Phones, config interface etc.
We are rapidly running out of options other than Change the SIP system which would be a fairly large expense or changing ISP which would be little or none. I would sooner they were on 2 degrees as whenever I've rung 2 degrees the first person I've spoken to has been able to resolve the issue - With Spark at best its the second person and they are usually hard to get escalated to.
I hope that we do find something other than the Spark network is causing the issue but its not looking good - I haven't spoken to 2Talk and I know that their support can be a little lacking at times too so its not impossible that they have blocked the IP address somewhere and haven't looked properly but assuming the phone people have done everything they say correctly then there isn't much left other than a Spark/2Talk issue.