I was thinking Gritzy Desert from PIT because of the Princess Shroob and now your new tip makes me think of the shroobs again. I'm pretty well stumped. Let's see if any others can come answer this while I think about it.
1. This area has a toad boy obsessed with video games 2. The mayor of this area changes by the time the game ends 3. This area maintains a pleasant climate all year round 4. This area is panicked when you first arrive
1. This place is a spooky environment. 2. A party member is obtained here. 3. Going anywhere but the set path automatically takes you back to the entrance. 4. This place is somewhere to the east of a town.