The simplest solution to get rid of horizontal stretching in full screen mode on a widescreen monitor would be to enable fixed aspect ratio scaling (or 1:1 scaling; whatever it's called) on your graphics card control panel or monitor.
OK, I just tried this, running nvidia-settings in Terminal, clicking DFP-0 in the lefthand side, and then selecting Aspect Ratio Scaled. It does work.
The difference I noticed is, while setting my screen resolution to 640x480 and then playing made the game fill the entire screen, the fixed aspect ratio made the game only fill the screen from top to bottom - on either side, there were large black margins. The panel, too, was completely visible.
So I guess it's a trade off between either true full screen but having to make a few clicks, or saving some time but not really getting fullscreen.
EDIT: Incidentally, I just finished trying all my Touhou games fullscreen (with the exception of PoFV, which doesn't run properly anyway, and IaMP, which I almost never touch), using both changed screen resolution and fixed ascpect ratio. I find changed screen resolution a more aesthetically pleasing result, and as it only takes a few clicks to set up and take down, not really that much effort is required.
However, in both cases, this is how my gameplay ran:
UFO and SA: Playing 72 FPS. Oh, did you want NORMAL MODE?
MoF and StB: No problems.
EoSD and PCB: Runs at 800 FPS. That's not an extra zero.