Our company provides merchant and fraud screening services. Recently
we have been setting up many accounts in the European marketplace. We
have already taken steps to register our company in Europe. My
question is on VAT. Considering that ours is a service and not a
product, do we have to charge VAT? What percentages? And how does it
work?

http://www.hmce.gov.uk/channelsPortalWebApp/channelsPortalWebApp.portal?_nfpb=true&_pageLabel=pageSupport_ShowContent&propertyType=document&columns=1&id=HMCE_CL_000346

Above link goes to UK Customs Website, Public Notice 741 'Place of
supply of services'. Section 19 has a list of a large number of
services and the relevant sections for how they are treated in terms
of paying VAT etc.

In general dependant on the service, it is either deemed to be
'supplied where performed' i.e. you pay VAT, or 'made where the
supplier belongs'.

Be aware that whilst similar, each EC country has slightly different
VAT rules and you should contact each country's tax representatives
for a definitive ruling on Place of supply. Also be aware that if you
provide taxable services to a country that exceeds its VAT threshold,
you will need to register in that country for VAT and appoint a tax
representative to deal with all of the paperwork etc.

Hope this is of some help.

O.