Yes it is legal
Monitoring email and internet use
In the UK, it is unlawful to intercept electronic communications unless the interception has been authorised, whether by a warrant, by consent, or by regulations. Regulations that came into force in October 2000 provide circumstances in which a business can lawfully intercept emails (and telephone calls) made on its own systems, such as:
Gaining routine access to business communications;
Monitoring standards of service and training;
Preventing or investigating crime; and
The unauthorised use of systems.
http://www.out-law.com/page-458
Note the last one - This is why many companies have an acceptable use policy so that they can then claim unauthorised use monitorring.
In practise in my experience - very few Europen companies monitor, it being illegal in many countries in Europe.
A lot of American companies monitor
In the UK it seems to be a bit of a mixed bag.