You must be using an older version of PS. CS3 doesn't have that size restriction.
Breaking it up into smaller pieces would certainly work, but it would be a little clumsy.
Regional maps in VTTs are not that small. In fact, one of the strengths of MapTool is that it practically has no maximum size. Realistically it does, but it depends on what is on it. That also is assuming that you are creating the map directly in MapTool instead of importing an external pic. Some of the tests we've done have been with maps that were a mile long and longer per side. As I suggested before, you should sign up at the various VTT forums and take a look at their capabilities and what others are doing if you are serious about getting into that market.