VAT on Services to Foreign Companies

In 1997 Rimsco Ltd. set up what we believe was the first Internet Service Bureau for Integrated Ledgers.
Due to the prohibitive cost associated with putting servers on the Internet in the UK (BT leased lines,etc.) at that time (and still very high now!), we utilise servers on server-farms in the USA.
We have now been approached by a middle-east based group of companies operating in several African states to use our service, which is multi-lingual/multi-currency, based on a common group currency of $dollars but using local currencies in each country. Our competition for this business is mainly US-based, and we are generally 10-15% cheaper than they are.
Now, our FD believes that we will have to charge VAT on invoices to the group. The rest of us are aghast, along the lines of "Charge VAT on use of American servers by a non-EU user in other non-EU countries! I don't believe it!". The company in question don't want to know about VAT, it is just a charge to them and it makes our service more expensive than the competition instead of cheaper.
Before we get embroiled with the VAT people for a ruling, we would be very interested in your members' comments.
R. M. Smith