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).