Since I can not post this answer in the WPML forum and as far as I can see nobody has answered the many questions about this there I thought I post my solution here.
Here's the problem:
When you set a static front page in WordPress and use the WPML language switcher to select a different language the front page will show the blog posts and not the static page.
Here's my solution:
Go to WPML > Languages and set the how to determine which language visitors see contents in to Different languages in directories.
There's a nice side effect though: I have a NextGen gallery slideshow (Flash based one) that could not retrieve any images when I switched to a different language. This is fixed now as well!
2 birds, one stone, one happy customer. :)