Would it work to fill the entire land with "dirt" first and then just cover it with other terrain types without using any special rules? You might end up with some dirt between other types of terrain but this is what HOMM I and II we doing too. And I'd guess they did if for similar reasons.
Also - how far did you go with auto-tiling? Can the effects of your work be seen somewhere?