We know they do. An orbit is a mathematical object, and elliptical orbits only exist in universes that have exactly two objects with mass in them. Add another object, even far away, and as far as we know[0] we no longer even have a closed-form description of resulting motion patterns.

And our universe has tons of matter with gravitational mass everywhere, few other types of interaction beyond gravity, and a vacuum that just doesn't want to stay empty.

--

[0] - Not sure if this was mathematically proven, or merely remains not disproven.