In Kanto, Team Rocket is kinda like the mob. They have people in high places letting them do what they want. (Like how some Silph Co. scientists worked for Team Rocket.) Then you beat Giovanni- making him retire to who knows where, before he goes to Tohjo Falls.
In Johto, Team Rocket being reborn was a rumor to most, even though you knew they were getting back together. Then when people had finally agreed it wasn't a rumor- it was too late. Goldenrod City had already been captured with no way in or out. Then by the time it had been open- there was a hostage situation, so no police could get into the Radio Tower. Then you defeated Team Rocket and they escape.
In Hoenn, there wasn't much people could do about Team Aqua and Magma. At first the worst they did was steal the Devon Goods and a Pokemon- and that was one person. You can't arrest an entire gang because of one person. You couldn't arrest Team Aqua at the museum either- they were just... there. What could you arrest them for? Trespassing? In a museum? Then there was yet another hostage situation at the Weather Institute where the people inside probably couldn't communicate to the outside. But even if they could, the bridge to the nearest city, Fortree, was blocked. Even at Meteor Fall's nothing could have been done, for a meteorite could be anybodies property. They're bases were hidden pretty well too. They were gone before the police could arrive at the scene of the stolen submarine. The only real time they could have been arrested was when the Legendary Fight was happening, but I presume they were a little occupied at the moment. Then Maxie and Archie disappeared without a trace.
In Sinnoh, Team Galactic hid behind a ruse of gaining cosmic energy to create a better world, like a power company or something. Nobody knew what was going on at the time, except that they were a weird group who did strange things, and a few minor crimes that were fixed. But the Inter. Pol. sent Looker to investigate their suspicous activity and then the whole 'dimensional' thing happened and to put it basically, Cyrus disappeared.
In Unova, Team Plasma led others to believe they were a peace faring group, against pokemon abuse, albeit the few bad eggs in their team, so the police didn't think much of it. Looker was sent to investigate this though- but arrived late. Ghetsis disappeared, after being captured by Inter. Pol. and being resued by the Shadow Triad.
But to put it all basically, the Police had good reasons if they were to be put under the laws that we have in reality. But still- to let the Bosses of villanous groups go? Even when they easily could have had them in custody?(Especially when they had Ghetsis in custody...) Sigh.
5 villains never found. Wonder what happened to them?