Android - Where are the SIM Lock settings stored on an Android phone?

The SIM lock stuff is in a separate ROM chip that is not part of the normal phone storage, AFAIK. It's manufacturer/device dependent. Definitely nothing to do with the baseband (and you can certainly flash other basebands).

I saw a professional in China unlocking HTC handsets via JTAG. A side effect with the unlock was the S-ON.

The SIM lock is stored in the Radio NVRAM, is not changeable, but they did the unlock by flashing a patched HBOOT with S-ON and that will report a different SIM lock status (my unlocked phone still says SIMLOCK in fastboot mode - another proof of that is that the fastboot mode now contains a Chinese URL)