To answer my own question, OMEMO requires the server to support "XEP-0163: Personal Eventing Protocol". XEP-0163 seems to be more or less supported everywhere. It is sort of amusing that it was originally intended for stuff like letting your contacts know what song you are listening too. Now that it is an OMEMO requirement it has for all practical purposes become mandatory.