There is no clear indication in the books that this use was invented by Dumbledore.
Here's what the Pottermore page on the Patronus Charm (written by J. K. Rowling) has to say (emphasis mine):
One of the most powerful defensive charms known to wizardkind, the Patronus can also be used as a messenger between wizards.
The Patronus Charm is one of the most ancient of charms and appears in many accounts of early magic.
The wording - "messenger between wizards" - and the charm being "ancient" leads me to conclude that the "messenger" use for it has existed as long as the charm itself.
Dumbledore is the first person to use it in the books:
“Should I go and get someone?” said Harry. “Madam Pomfrey?”
“No,” said Dumbledore swiftly. “Stay here.”
He raised his wand into the air and pointed it in the direction of
Hagrid’s cabin. Harry saw something silvery dart out of it and
streak away through the trees like a ghostly bird.
Harry Potter and the Goblet of Fire, chapter 28 "The Madness of Mr. Crouch", page 560, Scholastic.
After that, there isn't much elaboration on the topic of the originator of this use of Patronus Charm. However, the following passage from Deathly Hallows suggests that the "talking Patronus" can be learned by means other than Dumbledore or members of the Order:
“Can you do that talking Patronus thing, then?” asked Ron.
“I’ve been practicing and I think so,” said Hermione.
Harry Potter and the Deathly Hallows, chapter 9 "A Place to Hide", page 164, Scholastic.
That Hermione learned it by herself, with no explicit guidance from the members of the Order (though I don't deny that possibility), leads me to believe she learned it from a book, meaning that it has been documented, meaning that it must predate Dumbledore (since there's no indication Dumbledore ever published this feature of the Patronus Charm).
Voldemort's side doesn't use it because they don't need it.
Dementors are already their allies. The same page on Pottermore also indicates that most Dark Wizards consider Patronuses useless, though they can conjure them if needed (emphasis mine):
However, most [Dark Wizards], who become desensitised to the effects of the Dark creatures with whom they may ally themselves, regard the Patronus as an unnecessary spell to have in their arsenal.