NTT verio europe is a great provide, but requires some tricks when it comes to DNS Zonemanager changes for Google Apps (BTW: great tool, once you changed you never go back). Here are the necessary changes you need to make for NTTVerio:
put "ghs.l.google.com." in the "spec" field. (not "ghs.google.com" as Google tells you).
put "mail.yourdomain.com" in the field "Name". (not "mail" as Google tells you.)