It honestly seems like a quick and easy fix to a lot of these issues is just to add HP. Voss has 80 HP but Ambuscade has only 50? Give Ambuscade 80 HP and he'd naturally be more challenging.
Not really. It would be a longer fight but nothing in the deck would change. Ambuscade playing 4 cards-you-have-easily-countered is not much worse than Ambuscade playing 3 cards-you-have-easily-countered.
Good point. I think I'm going to thin his deck a little, personally.
No I disagree. The longer the fight is the more potent his trap are. Multiple flipped traps in the deck need time to resurface. What makes Ambuscade so easy normally is because the fights are so short that the flipped traps never make an appearance, making those villain rounds essentially free turns, and you can rack up quite a few. More health is a perfectly good and simple solution to houserule with.
He still doesn't prevent hero build-up, or really even slow it. That extra health will often last one round because Amby tends to do damage to start, then at times he bursts again, but at no point does he stop you from outpacing his damage. Voss at least makes you deal with his minion reduction, and possible swarms, but Ambuscade's traps aren't nearly threatening enough to turn the tide.
A better solution to more HP is just having him play a second card each turn. That way he has a much better chance of keeping up with the heroes and being a real threat.
Flipped Trap cards play more cards. Going from 50 to 80 with the DR he can weild is not something to just sneeze at. Frankly he doesnt need to slow down the heros, and I'v had many a close game playing him on advanced (which should be his standard mode imo).
Another small houserule that I employ is to play a card after you shuffle a trap back into the deck and after one shows faceup on the deck. Now thats a real threat. That rule servers two purposes. One, it eliminates "free turns". Second, it speeds up his deck. So he is more likely to find his nasty combo cards and more likely to set off the traps. That one I like a lot more than just a flat HP increase.
It's a start, but it still doesn't really do it for me, because (1) Ambuscade's Traps aren't anything that would really be scary even if they just hit you immediately, and (2) while more HP make the game longer, with most villains (including Ambuscade) they manage to increase difficulty (marginally) without increasing the challenge. To explain what I mean a little:
Ambuscade has no ability to destroy your cards in play, very little ability to ramp up his threat over time or make a comeback, and almost never presents a meaningful question of target priority - you'll take out the force field, then the big weapon, then the robot, then the little weapon, then the shield in that order, almost every time you have to pick. So, when a game against him goes longer, the last point means that you don't need to keep thinking of new tactics, and the middle one means that he's not upping the stakes. Both of these things combine to mean that a longer game with Ambuscade will ask no new questions, and thus does not deepen the puzzle (thus, the challenge). Of course, the first one makes even that irrelevant, since all your combos stay put, so you can just shut down his attacks and do massive damage effortlessly, which is why I say it doesn't actually increase the difficulty by 25% like you'd expect, either. With 20 HP or 100, a villain with no comeback condition and no stuff destruction only gets very slightly more difficult, since almost all heroes in SotM get radically more powerful as they get their setups into place. The only exception would be someone like Iron Legacy, who is emphatically not hard because of his HP total, but because he's designed to end the game before you ever see your setup happen (and if the heroes do get set up anyway, he crumples). That's why most of the scariest villains are that way because of crazy amounts of comeback power, so that you're still in danger up until the very last hit: Cosmitron and the Matriarch might draw into that 15-card string of mooks, while Voss and The Chairman have rightly-feared abilities to undo most of your hard work by dropping massive setups on top of you. All of these tricks increase the difficulty significantly, while adding some to the challenge, as well.
My favorite villain designs, which I consider to also increase the challenge notably as time goes on, are ones such as The Ennead, Citizen Dawn, and La Capitan. All of these have some degree of stuff destruction, to keep you from resting easy, and will have multiple targets which you cannot take out in one turn out at a time. Thus, you must both work the puzzle of target priority and that of resource management at the same time, and each turn it goes on, the puzzle has a chance to get nastier, even as you fight for a chance to have better methods to use against it. If you gave any of them a bunch of extra HP (and, indeed, Dawn and La Capitan's flips both do simulate more health), you'd be in real trouble, since unlike Ambuscade, their games do not simply degrade in challenge every turn.
Of course, my preferred Ambuscade fix is just to set H=3, run him against 2 heroes in a resource-taxing environment, and watch the sparks fly... or to run him alongside a more credible villain with six heroes. So, my tastes are certainly not for everyone, either!
Ironic
My current Ambuscade house rules fest has been:
Play a card when you shuffle a trap into the deck.
Traps gain destruction:
The one that hits one hero destroys all their cards in play.
The one that hits all heroes destroys one card from each hero.
It makes the traps something you seriously fear.
But really, if you use play a card when you shuffle a trap and add "at the end of the villain turn play the top card of the villain deck" to both sides you get pretty dang good results.
Trying to shuffle the traps into his deck has been a problem for me. You can typically see where the trap is in the deck because it is going against the grain of the natural curvature of the deck. It makes it very difficult to shuffle fairly.
My house rule is I just trigger the trap when the card is drawn.
I do this too with a "play the next card of the villain deck" tag at the end 
I ike the shuffling in, but I have the traps play the next card after you shuffle them in. I like that they punish you for revealing his deck.
For shuffling Ambuscade I like to shuffle his traps in upside down instead of face up. It makes it harder to actually see when the trap is coming up.
Also, my house rule is Ambuscade starts with H-1 traps set in his deck. However, I really like phantaskippy's idea that the traps blow up stuff, too.
Ironic, I totally agree with your explanation of why Ambuscade struggles. You are right that adding HP is not the answer, but I don't think your suggestions solve the problems that you pointed out.
I've started using Ambuscade as a Villain that goes up against only 2 heroes. H was still equal to 3.
I've also played a game where I added him in with Grand Warlord Voss, up against 5 heroes. I just played it where both Villains go, then the heroes. That worked really well.
The real nasty card in Ambuscade's Deck is Charged Attacks, thus if you want a really nasty game against him just add that card in play in his setup and make it indestructible and then you get to cringe when the environnment targets his mines...
What was really fun was working on the Ambuscade conversion to Vengeance format.
Charged Attacks when Omnitron is in the game. . . ouch.
I have taken to not resetting traps between plays of Amby's fights. So in one fight you defeat him and he has three traps already seeded in his deck then the next time you play him he still has those cards seeded in his deck. I wouldn't really say it makes him harder since his traps aren't super threatening but It does make it a little more exciting knowing that this villain has already laid out some traps for the heroes.
The house rule we've been using for Ambuscade is as follows:
Treat traps as double-sided, ie. The card text on both sides. I just always shuffle them into the deck face-up all the time. (Though I've been thinking about ordering some extras and just putting them back to back.)
This makes it so he gets these "extra" one-shots. I feel like it scales him up a bit, without making things too complicated.
Mechanically, I guess this is similar to the "play traps when they are drawn, then play the next Villain card."
I used to do that then I got seven traps blowing up in my face in one villain turn, I will not do that again Ambuscade has to many extra card plays and trash shuffling cards for this to not just make him fiddly and dangerous for stupid reasons.