Weird, never got such issues. OMEMO is what I use in my DMs, and it was designed with offline messages in mind (and it does work for me). I know this sounds like "works on my machine", but this is the first time I hear about this happening consistently.