Here are my picks:
Jafar and Maleficent - Andreas Deja modeled Jafar after Maleficent. They both have pet birds and sorcerers, and they both turn into gigantic creatures when battling with the princes. They have a similar taste in clothing and similar personalities. They both even have similar lines, such as "say hello to your precious prince Ali" - "you little fool, you thought you could defeat the most powerful being on Earth", and "you poor simple fools, thinking you could defeat me, *me*! The Mistress of All Evil! Well, here's your precious princess!" I think Jafar can be hysterical at times, but he is very cool, calm, and collected, so this probably would not bother Maleficent, and Maleficent can be a little hysterical herself at times, though she is much more mature.
Hades and Ursula - For the reasons you suggested.
("There's the similarity in color schemes (purple/blue/gray), they're both kind of seductive when presenting their Faustian (I added that) offers and they both have a wicked sense of humor. Oh, and there's the Musker/Clements connection, of course."
Judge Claude Frollo and Lady Tremaine - They both abuse an adopted child and give them chores to do, they are both self-righteous, manipulative, uncaring, sadistic, French, and self-pleasuring. They even look similar.
Governor Ratcliffe and the evil Queen - This is an uncommon pairing, but it could work. The evil Queen is very elegant and Governor Ratcliffe is very polished, and Governor Ratcliffe does remind me a lot of the Huntsman, so does Gaston, Clayton, and Captain Hook, but yeah. They both also have a pet companion. I also nix the idea about the evil Queen with Gaston, besides Gaston is obnoxious and is not around the same age as the evil Queen is, and I cannot imagine the evil Queen being anyone who is ranked below a king, and do not forgot that the evil Queen does turn into an ugly hag when trying to poison Snow White, so this might be a disadvantage for Gaston. I would also want to say that the evil Queen is too involved with her looks to really be with a guy, so this might be an advantage for Governor Ratcliffe, since he is too involved with his money.
I can also imagine the evil Queen with the Horned King, since they both have cauldrons, both are monarchs, and both are grotesquely evil, but since he is not human, she might not like that, she is too vain about looks, so this needs to be considered. I can also imagine her with Judge Claude Frollo, but he is much more suitable with Lady Tremaine, or with Emperor Shan-Yu, but he might be too superficial for her, but the pairing might be a good idea.
Gaston and Drizella - Drizella is the black-haired "ugly stepsister", but she is not that ugly. Gaston might not willingly choose Drizella, but when he gets to know her, and notices that she is just as vain as her looks and obnoxious as he is, he might give her a chance. I do not know anyone person I would want to pair Anastasia up with, but I did not like when she dated the Baker, because she is supposed to stay evil, and she is better that way.
Percival C. McLeach and Madame Medusa - They are both from the same series. They both kidnap and abuse a child, who the Rescuers aid. They both have a reptile sidekick. They both have trashy lifestyles and guns. They both recklessly drive.
Sykes and Madame Medusa is also a good idea, but Sykes is a loan shark, and Sykes might not like the uncivil life Madame Medusa has, or the psychotic behavior she possesses. I also do not know how Roscoe and DeSoto and Nero and Brutus might get along.
The King of Hearts and Cruella De Vil - Cruella De Vil has a small, weak, mousy, and henpecked husband like the King of Hearts in the original "101 Dalmatians" story, and the King of Hearts is already married to someone like Cruella De Vil, so the relationship would be familiar. The King of Hearts is also probably very rich, and Cruella De Vil is too greedy with money, so it does fit, and the King of Hearts would probably enjoy being with Cruella rather than the Queen of Hearts, because she is not as hot-tempered as the Queen of Hearts is, she is still eccentric, but not as much.
Captain Hook and the Queen of Hearts - They are both elegant and pompous monarchs. They both can be hot-tempered at times, which is a downfall for their potential relationship, but they can be suave at times, too, and Captain Hook can be much more suave than the Queen of Hearts can be, so it could work. They are also villains from Fantasy lands and metaphorically teach the children how to be mature in villainous ways. The Queen of Hearts is already married, but I do not think that would stop her from dating Captain Hook, and I do not think Captain Hook would even take the marriage into consideration. Captain Hook might deserve someone who is not fat, but the similarities between the two villains would probably make him more and more interested.
Captain Hook and Cruella De Vil might also be a good idea, since they are both boastful, eccentric, and have a sense for fashion, but I do not like the pairing as much for some reason. Captain Hook also needs someone as smart as he is. Cruella might be, but I prefer the pairing of Captain Hook and the Queen of Hearts, since they have an essential brother and sister relationship, and the King of Hearts and Cruella De Vil would be an interesting choice.
Yzma - I do not know who I want to pair Yzma up with, but she needs someone with pizazz. I would want to pair her up with Jafar, but since she is so old, he might not like that, remember he was somewhat interested in Jasmine, and Jafar is already with Maleficent. Yzma also deserves someone who is much meaner and much more deceit than Jafar is, so maybe the Horned King would probably be better, but he is not human, so I do not know. I could only think of Destane, who is from the "Aladdin" cartoon show, but I do not know much of him, but he was so ruthless and fearful that even Jafar was afraid of him, and he did have much power, of course that was before Mozenrath stopped working for him and took his power over.
I can put the Horned King also with Maleficent, since the Horned King and Maleficent both have horns and are interested in magic, similar elegant personalities, and treat their servants cruelly, but Jafar and Maleficent make an awesome couple.
What do you think?