Oh, now that could be the clincher.

I knew it. This thread should be mirrored under the "Spousal Approval" thread!

Yes, driving is easy, albeit high gas prices, and driving makes it easier to explore small towns (which to me is more than half the fun). A lot of the rental cars are diesel/gazole, reducing the bite a bit. Depending on your inclination, you might think about some train travel, too. RailEurope offers some multi-day "select" passes that let you pick any group of three countries (under their scheme, BeNeLux counts as one country), so for example you could hit Belgium, Netherlands, Luxembourg, France and Germany on a single pass. That can also help if airfares are hugely cheaper into one city (say take the plane to Paris or Frankfurt, then take Thalys/TGV or ICE train to Netherlands) and you maybe don't want to drive such a long haul.

I wish you good luck in your mission! I've been there!