@gijs Could it be because you have your instance configured as "single user"?

Try this in config.php, commenting the "single user" line:

$config['site']['profile'] = 'community';

Reload, and check if "Messages" appear on menu.