I did some theorycrafting in the Dedede topic about Brinstar. JJ is easily the best CP, meaning it's probably going to be banned by any sensible D3, and I assume Orpheon would probably be good against him too. As for Brinstar...
It's too small to camp, which usually isn't a good thing against Dedede. However, the fact his CG is basically useless here removes most of the need to camp him. (The other reason to camp him is simply because he's a gigantic, slow-*** target.) There's no way he can edgeguard you because the terrain is so broken-up and you can fly through the floor. And you could probably camp quite effectively if you focus on keeping the stage split by keeping the "energy tanks" broke whenever they reform, like you took JJ's platforms and widened the gap between them.
All theoretical, though. Lain always plays his D3 against me instead of IC's, though, mebbe next time I see the MI guys I'll try Brinstar to see if it's as effective as it seems it could be. I don't see much reason to BAN it, though. Why would Dedede want to take ROB to Brinstar? I'd ban Rainbow Cruise before anything, FD is obvious, and I'd look out for any stages with walls or walk-offs (such as Delfino) before Brinstar pops into my mind. (I actually like Delfino, but most people don't.)