There aren't enough numbers provided in canon to be able to explain this definitively, but we might be able to make an educated guess.
In the episode, Neelix talks to Dexa, who provides the background to the colony:
Neelix: It must've taken years to do all of this!
Dexa: Almost five. It still isn't finished.
Neelix: Where did the technology come from?
Dexa: We arrived here with a caravan of six ships. We disassembled all but one of them and modified their components.
The episode takes place on First Contact Day in 2378. This means they started building the colony around 2373.
The Haakonian occupation of Talax ran well into the 2370s, but Talax was only occupied as the war ended in 2356. Dexa mentions the occupation, but doesn't mention anything else, so it could be they left the planet shortly after the occupation (let's say 2357).
So we have a reasonable time: 16 years. What about distance?
There is no canon source for that, but Geoffrey Mandel's Star Trek Star Charts estimates them based on the information the episodes provide, so it's as good an estimate as any. Based on his charts, Talax is estimated to be around 46,100 lightyears from the colony.
So now speed. Given these numbers, the caravan of ships would have to have been traveling at least 2,881 times the speed of light (c). The warp factor of a ship traveling below warp 9 is calculated as follows:
If we use this formula, it turns out the ship would've been going at warp 10.911, a paradox since the scale caps at warp 10. To resolve this, the speeds corresponding to warp factors above 9 are increased exponentially. There is no established formula for that, but in "The 37's", Tom Paris mentions warp 9.9 being about 4 billion miles per second:
Amelia Earhart: How fast?
Paris: Warp 9.9. In your terms, that's about four billion miles a second.
That's about 21,000 c. If that's accurate, the warp factor formula at 9.9 would then be something like:
So if only the numerator on the root increases linearly (which would still increase the speed exponentially), every .1 warp factor after 9 increases the numerator on the root by 0.336.
If that's a fair estimate, a ship traveling at warp 9.225 the entire time should be able to make the journey in 16 years. Not exactly an easy requirement, but not extremely out there, either. Keep in mind the Talaxians would have the same opportunities for short cuts that Voyager had, and they might've been able to significantly shave a bunch of time off their journey as well.
It's a bit easier if we use your estimate of 31 years: this means they would only have had to travel at 1,487 c. To do that, they'd just need warp 8.9.