Shipping suddenly not working

Hi All,
I have recently been having issues with our shipping.
The error is not specific to one type of address or shipping class.
I can generally describe it as just not functioning properly overall, the problem encountered depends on the region selected and quantity/ weight of the order making it difficult to isolate because the problem appears differently depending on the parameters selected.

This suddenly seemed to have happened after months of our shipping displaying correctly. The only change that was recently made was to our tax’s, but this shouldn’t affect shipping as far as I know.

The problems are one of two;

Either the incorrect shipping options display

or

“No shipping options were found for XXX” displays.

I have verified the shipping weights and and settings on the back end having tried to trouble shoot this for some time now. I tried debug moe but this isn’t providing any insight.
I am beginning to suspect it is being caused by some sort of bug.

Any guidance would be appreciated,
SG