Yes, you can make maps bigger. In fact, most TFTD crash recovery sites and the second stages of alien bases are 60*60*4. The map doesn't have to be square either, you can make it 40*70*4, for example (TFTD shipping lane terror sites). Also, the 255 MCD limit only applies to a single map chunk, from what I understand. You can abuse the addUFO command to create maps that have way more than 255 unique tile types (somebody more knowledgeable will hopefully explain the limitations of this method).
edit: By the way, are you remaking alien bases to be 4 floors deep? I'm asking because I'm doing the same thing, pretty much - remaking alien bases to be 60*60*4, like in TFTD. So far I have compiled an MCD set with some new graphics and made like 6 map chunks, maybe we can collaborate?