Hi Brian
Apologies I probably should have posted when this was finalised. It turned out perfectly. Unfortunately the project itself is mounted in my father's boat and since it was a surprise gift it appears I didn't take/keep progress photos to attach here, but can step you through the experience.
The original switches were de-soldered and replaced as you suggest. This was time consuming but not difficult. On the board I had there were surface mount components under the switches in between their legs so it was a case of firstly getting the bulk of the solder off with a sucker and some braid, but that left them still stuck so it required heating the legs from one side and lifting from the other with pliers rather then levering them out and risk damaging those. The bare holes could then be cleaned up from the component side with braid. The replacements went in with ease and poke through drilled holes in the enclosure quite neatly. To drill the holes I made a template after the new switches were in place, with holes poked in cardboard, then marked out where to drill with a sharpie using that template. I mounted the shield to the enclosure using M3 screws through the holes on the LCD board which extend through the shield to make that possible, then pressed the Arduino into the regular headers from behind then drowned it all in hot glue to try to make it a little more rugged. My enclosure is mounted vertically, so I thought that should be okay. It went into the catamaran April 2012 and regular sailing with this mounted to a bulkhead has proven that to be the case, at least to date.
I did make one terrible mistake that I'll call out in the unlikely event someone else on the planet has the same bad idea. As part of the "ruggedisation" I initially masked the switches and sprayed the whole thing with
circuit board lacquer. As it dries this stuff spreads out, and got under the masking tape and into the new switches, locking them solid. I used a full can of board cleaner (and what seemed an eternity of washing) to get the lacquer out of the switches and they've worked fine since, but it's a lesson learned.
It's disappointing that every LCD shield I've seen since also has this limitation but if they came out with the taller switches they'd be a bit goofy to use when there is no enclosure so there's a case to be made both ways I suspect

Cheers & good luck with yours, Geoff