Despite the fact that he has cute Happiny and perky Sudowoodo, he should have left after Battle Frontier.
What the anime needs is another male companion for Ash and Dawn that does not crush on every girl he sees.
EDIT: Rank up! And how ironic, in a thread that talks about Brock.
I think that's a pretty good idea. I don't want Brock to go, but I think that they could add in another character. So it would be like when they had Max. Except he wouldn't be a twerp. I could imagine like a really cool, popular-kid kind of person, that's traveling with Ash because they end up being child hood friends that haven't seen each other in a very long time. Someone that has an attitude like Paul's but not as ... rude... if you see what I mean. Just very cool. And a lot less... moral. I think they could work that into the anime, and in the end have some corny theme of him turning into someone like Ash, or whatever.
And about Reggi, I could see them traveling with Reggi, to stun Paul, except I think it should only be for a limited time. Like maybe Reggi's going to a Breeder's convention, and happens to run into Ash, so they have one arc with Reggi, maybe 10 or 15 episodes or so. And after the convention, Reggi goes back the way they came, and Ash's friend happened to be at the convention as an audience member or something and then they start traveling together with what I said in my first paragraph. I actually like these ideas lol.