After quite a bit of confusion and mucking around, it turns out that Magento Table Rates out of the box use prices excluding VAT for the price vs. destination rule-set. This was regardless of catalog prices including tax under the Tax configuration, and prices displayed including tax. So we had to work out the order value minus the current VAT rate of 20%.
I would highly recommend anyone planning to use table rates with Magento, to use this free extension: http://www.magentocommerce.com/magento-connect/webshopapps/extension/604/webshopapps-matrixrate–the-original-multiple-table-rate-solution–certified-bug-free. It adds another shipping method to your Magento Installation, based on the out of the box table rates system which Magento uses, but it’s a lot more stable, flexible and best of all FREE!