Welcome to WebmasterWorld Guest from 18.104.22.168
In brief: they don't have to charge you VAT.
(We're talking about a UK company providing web hosting for a client outside the EU, right?)
If they choose to charge you VAT, then I don't know if you can reclaim it - but it's much simpler for you if they don't charge it to you in the first place.
There's info on this on HM Revenue & Customs website, but it's a bit dense - I suggest emailing HMRC.
Once you've got an email from them confirming that the hosting company doesn't have to charge you VAT, I can't see why they would insist on doing it - probably it's just some junior who thinks they have to charge VAT to everyone.