Why are dementors natural allies of Voldemort?

Question

When Azkaban is broken open, the Lestranges will be honored beyond their dreams. The Dementors will join us ... they are our natural allies ... we will recall the banished giants ... I shall have all my devoted servants returned to me, and an army of creatures whom all fear ....

(Harry Potter and the Goblet of Fire, Chapter 33, The Death Eaters)

There is a perfectly good out of universe reason why Dementors should be allies with the death eaters — no dark lord deserving his title is without an army of nightmarish creatures at his command, and Dementors are set up as being more nightmarish than most.

But, in universe, is there any particular reason why the Dementors and Death Eaters should align so closely?

Answer 1

They both spread death, darkness, destruction, dread, and despair. The Death Eaters allow the Dementors to take people's souls - the Ministry doesn't. They're both... evil ;)

The Dementors feed off of despair. Voldemort's army spreads it, allowing the dementors to breed. The Dementors take care of the Death Eaters enemies, taking their souls, and demoralizing the rest of the population. It's mutually beneficial to both of them.

The Prime Minister sank, weak-kneed, into the nearest chair. The idea of invisible creatures swooping through the towns and countryside, spreading despair and hopelessness in his voters, made him feel quite faint.
_{Harry Potter and the Half-Blood Prince, chapter 1}

So we see that they're causing despair and stuff.

We also see that they breed more once Voldemort and his followers grow powerful:

"And if that wasn't enough," said Fudge, barely listening to the Prime Minister, "we've got dementors swarming all over the place, attacking people left, right, and center..."
Once upon a happier time this sentence would have been unintelligible to the Prime Minister, but he was wiser now.
"I thought dementors guard the prisoners in Azkaban," he said cautiously.
"They did," said Fudge wearily. "But not anymore. They've deserted the prison and joined He-Who-Must-Not-Be-Named. I won't pretend that wasn't a blow."
"But," said the Prime Minister, with a sense of dawning horror, "didn't you tell me they're the creatures that drain hope and happiness out of people?"
"That's right. And they're breeding. That's what's causing all this mist."
_{Harry Potter and the Half-Blood Prince, chapter 1}

Also, (Kudos to @TheDarkLord for mentioning this!) Voldemort allows them many more chances to use their powers and enjoy themselves:

"The rest of us sleep less soundly in our beds, Cornelius, knowing that you have put Lord Voldemort's most dangerous supporters in the care of creatures who will join him the instant he asks them!" said Dumbledore. "They will not remain loyal to you, Fudge! Voldemort can offer them much more scope for their powers and their pleasures than you can! With the dementors behind him, and his old supporters returned to him, you will be hard-pressed to stop him regaining the sort of power he had thirteen years ago!"
_{Harry Potter and the Goblet of Fire, chapter 36}

Answer 2

If Voldemort and the Death Eaters were to gain power, a massive buffet of Muggles would be available to the Dementors. Voldemort cares about magical blood, he's not about to let them just soul suck all the opposition, as evidence by his speech at the final battle. Eventually he will turn his attention to the Muggles, and the Dementors are the perfect creatures for the job.

Answer 3

The Dark Lord offered more victims and conditions they thrive in.

Under the Dark Lord’s rule, the Dementors had more victims, as well as more of the conditions they thrive in. The Ministry had them confined to Azkaban, but when the Dark Lord took over, they were allowed to go anywhere that the Dark Lord or the Death Eaters wanted them to spread despair.

“And as if all that wasn’t enough,’ said Fudge, barely listening to the Prime Minister, ‘we’ve got Dementors swarming all over the place, attacking people left right and centre …”
_{^{- Harry Potter and the Half-Blood Prince, Chapter 1 (The Other Minister)}}

They were also given the courtroom where Mudbloods were tried, and they were given particularly uncooperative Mudbloods to suck the souls out of completely.

“Dementors, he thought.

And as he reached the foot of the stairs and turned to his right, he saw a dreadful scene. The dark passage outside the courtrooms was packed with tall, black hooded figures, their faces completely hidden, their ragged breathing the only sound in the place.”
_{^{- Harry Potter and the Deathly Hallows, Chapter 13 (The Muggle-Born Registration Commission)}}

In addition, the general conditions under the Dark Lord’s reign were better for Dementors to thrive in. Dementors thrive in conditions of hopelessness and despair, and when the Dark Lord took over, there were many of the Dark Lord’s opponents who were hopeless and in despair.

“Dementors are among the foulest creatures that walk this earth. They infest the darkest, filthiest places, they glory in decay and despair, they drain peace, hope and happiness out of the air around them.”
_{^{- Harry Potter and the Prisoner of Azkaban, Chapter 10 (The Marauder’s Map)}}

The Dementors were only the Dark Lord’s ‘allies’ out of self-interest - they had many more victims, and the atmosphere was more conducive to their ability to thrive.

Answer 4

From harrypotter.wikia

"Dementors hold no true loyalty, except to whomever can provide them with the most people to feed off."

Dementors are natural allies to a Dark Lord because a Dark Lord provides more people from which to feed.