A post-playtesting follow-up. I played a version of Mercenary that allows you to discard any number of non-victory cards. It's exciting and interesting at $5, capable of being very strong but not so reliably strong that it dominates. It's a gamble discarding Silvers this way, because you can get back green cards for them, resulting in a net loss. But sometimes it works. Discarding Golds this way, however, is probably a mistake. It also makes colliding terminals useful. As intended, the card weakens as the quality of your deck improves.
Where it really comes alive is in large hands, as you'd expect. I tried it in a heavy Tactician/Envoy game played some pretty long turns discarding upwards of a dozen cards for +$12, redrawing 12 cards including another Mercenary, and doing it all over again. It's even good just for setting up the Tactician turn in the first place, as it lets you accrue some money to spend before the Tactician discards your hand. Very powerful, but I lost that game anyhow, probably for lack of any source of +Buy beyond what the Tactician itself offers. (Also because I was dithering around trying to get megaturns instead of, you know, trying to win.)
Even better was a test game with an Alchemist stack. I built a deck with lots of Alchemists, two Potions, two Mercenaries, and a smattering of Silver along with the initial Coppers. One Wharf and a Hamlet or two got me the +Buys I needed. First the Alchemists would draw most of my deck, then the Mercenaries would discard it twice over, with the Hamlets and Wharf providing +Buys as they came up. I took care not to use Mercenary on the last Potion, lest the Alchemists get shuffled back in.
It was a very effective strategy but took possibly too long to set up (setting up Alchemists alone takes some time) and more vulnerable to greening than you'd think. Before long, the first Mercenary would do fine, but often I'd have a mostly green hand for the second to work with, if I even managed to find it at all. After these test games, I'm convinced the "non-victory card" clause is crucial to keeping the card's power in check. Although I've probably made it sound overpowered in these large-hand games, you really don't get very many big turns before it starts to peter out.
Under more ordinary circumstances, with average hand sizes, it feels like an average $5. You probably don't want to buy one all the time, especially in heavy trashing games or rush (Gardens/Duke/etc) games, but it makes a competitive $5 card in most other decks. In large hands, it shines in the way that Bank and Forge do, but once you start greening, it's not long before you wish that Mercenary was a Secret Chamber instead.
In other words, it works precisely as intended and is probably nicely balanced. Thanks for the idea.