It's probably in your best interest to have all the pieces done seperately and then just piece them together yourself. This would not work so well for the maze, though.
The most expensive part of the vinyl cutting is the size of the sheet of vinyl being used. If you pack them all in tightly, you use less vinyl and the cost is lower. Besides, if you want multiple colors it'll take multiple sheets. So you wouldn't be paying for just 1 piece of sideart if you got it positioned at full size. You'd be paying for 3 or 4.
It would be best to print just the maze at full size and then pack the characters, dots, etc. onto smaller sheets as small as possible.
Big images are usually not a problem, though. I can't speak for conseit's equipment, but these things are usualy cut on plotters. The vinyl comes off of a roll that can be up to a few feet wide and as long as you need it to be.