Why must the ultimate theory of the universe encompass both? Do we know that there is an ultimate theory of the universe? Could GR and QM be wholly separate with no unifying connection?
What does this mean? Is it mean that Universe have insufficient rules, so there are phenomena which do not follow any rules? Is it possible to devise an experiment whose results would be totally fundamentally irreproducible?
Or you mean that Universe has strict rules, but human's ways to write these rules are flawed and insufficient to grasp in a full a fractal nature of mythical rules of Universe?
So it doesn't have to be a combination of GR and QM, but it does have to be something which is at least as good as GR and QM respectively in their existing domains of explanation.
It would be a different situations if the theories actually covered different domains of experiments, but neither define such a restriction (and it wouldn't make much sense to either of them).