Effectively zero, but it takes a mental stretch to get there.
When you're dealing with a gas, lower pressure means that there is a longer mean free path, meaning the atoms/molecules can be expected to go longer and longer between collisions. You can get this either by spacing out the particles more (lower density) or by slowing them down (lower temperature). As this time between collisions increases, your system looks more like a bunch of particles moving in one direction, rather than a group of particles "sloshing" back and forth. In this limit of zero pressure, you don't get interesting sound wave propagation any more, and I'm pretty sure this is what your intuition is guiding.
Liquids, on the other hand, have great promise. Liquid helium-II (superfluid helium) is very weird--it can flow uphill to escape a container, and it will conduct heat better than any known material. This heat conduction is considered to be carried by sound, although you're more likely to encounter the term "phonon" in the literature. Phonons can be observed at very low fluid pressures, meaning that sound can propagate at very low pressure in this system.