I am not clear in what sense do you mean “Could a universe with purely Newtonian mechanics exist?” but here is my understanding of the situation.
In order to answer this question one must be based on established laws we know from our experience with our universe. It is only through these experiences that we can make inferences to situations elsewhere.
We know from our universe that there are two scales of great importance:
(i) Microscopic scale: This has taught us that for a rich universe, with ‘endless’ diversity and variation, it cannot be following rigid rules with yes or no type of choices. An inflexible universe like this would reach its final destination very quickly. It would run out of ‘ideas’ so to speak. Our universe achieves this diversity and flexibility we observe, via unpredictability and uncertainty. By this I mean that our universe operates on the basis of the laws of probability. Tiny details mater, and this is achieved by the extremely small size of Planck’s constant for example. This scale is ruled by Quantum Mechanics.
(ii) The macroscopic scale:**This is where the universe uses averages and effective collectivism in order to control **the large, and detail is not really important. This part of the universe makes no contribution to the diversity, flexibility and freedom we observe in nature. Things seem to be ordered and follow sort of rigid laws (Newtonian mechanics.)
However, it is impossible to reach scale (ii) without passing through scale (i). But scale (i) is ruled by the laws of quantum mechanics. For this reason one could conclude that an alternative universe would stagnate and reach self destruction relatively quickly.
Some people have done calculations for atomic stability by assuming smaller or larger values of Planck’s constant, or different Coulomb force law etc. They found that the atoms would not be stable under such variation of the laws of physics. One simply needs to look into the details of atomic structure, and their dependence on Planck’s constant, in order to realise the instability problems.
In conclusion: No, a purely Newtonian universe could not exist. Perhaps in my imagination, but this would be pure utopia.