Ok, what worked was this (in menu item params > "override: Parameters: Alpha-Index, Search, Filters"):
"Custom AI Character Aliases" > "a~aAäÄ!!o~oöOÖ!!u~uüUÜ!!".
(instead of setting these params per menu item I could have done it globally or per category aswell, I guess..)
This lets my "Ö"-items appear inside my "O"-item-list and the client is happy with it.
What did not work as expected, however, was this:
"Custom Alpha Index List" > "[default]=a,ä,b,c,d,e,f,g,h,i,j,k,l,m,n,o,ö,p,q,r,s,t,u,ü,v,w,y,z!!0,1,2,3,4,5,6,7,8,9"
AND
"Custom AI Character Aliases" > "ä~äÄ!!ö~öÖ!!ü~üÜ!!"
which would nicely separate "Ö"s from "O"s. Any idea why this is (not) happening?