On the way I did find some very useful websites, which I shall share for others on a similar mission:
- Some very nice pre-made PDFs of hexes and others, including grids with small hexes overlaid with larger ones: http://mojobob.com/roleplay/props/mapping.html
- An online gridded paper generator! Very cool, but unfortunately doesn't do numbered grids: http://incompetech.com/graphpaper/
- An inkscape extension for generating hex grids: http://www.lysator.liu.se/~perni/iboardgameexts/
Here's the PDF of my hex paper anyway, so you can see what I ended up with.
Addendum: I just started filling in those hexes, probably for the first time in 20 years -- what a joy!