I think I've pinpointed the issues for my particular usage.

Changed store to display prices without tax.
Customer from Belgium with 21% VAT rate set as above.
Threshold £130

Sub-Total: £129.17
Royal Mail International Tracked (Shipping to BE): £14.35
VAT 21%: £30.14
Total: £173.65
CORRECT

Sub-Total: £130.21
Royal Mail International Tracked (Shipping to BE): £14.35
VAT 21%: £3.01
Total: £174.92
Correctly stopped including VAT on cart contents but still adding VAT to shipping.

If shipping is increased to £132
Sub-Total: £130.21
Royal Mail International Tracked (Shipping to BE): £132.00
VAT 21%: £27.72
Total: £317.27
Correctly stopped including VAT on cart contents but still adding VAT to shipping.

So it can be seen that there are two issues.

First is that the net price is not being used when prices are displayed inclusive of VAT, and that stops any VAT being added or dropped from the total when cart contents are below the threshold because it is being assumed the price in the cart is without tax.

Second is that the shipping is being accounted for separately for calculating VAT.
When the cart contents are above threshold the VAT is still added to shipping if a taxable class. However the threshold for not including VAT is not being used on the shipping fee if it alone is above the threshold.

I tried out the Deny function and it works as you'd expect from the above - it basis whether to show or not on the price displayed in the cart, regardless of inclusive or exclusive of VAT.

I'm assuming no-one else in the UK is actually using this method to add vat for EU orders - rather it's being used to set a minimum price for orders to avoid the VAT/administrative implications.

For my situation, this is how I need it to act to exclude VAT over a certain amount for specific zones.
*Store must show gross price including taxes to customers by law.*

Use the cart price without VAT for threshold calculation, not including shipping.
If cart total is below threshold, add relevant tax rate to both cart total and shipping.
If cart total is above threshold, exclude all tax from both cart total and shipping.

Is this something that can be accomplished with this method or is a more complex mod needed?

TIA