Turns out that the procedure for enabling Visual Voicemail with Galaxus Mobile is the same as for TalkTalk.

In my case their database entry was somehow stuck and I first needed to send a VVM OFF to 935 before starting the procedure.