May is traveling to Slateport City in style: onboard a giant cruise ship that has the Grand Festival's prize Ribbon Cup on display! Officer Jenny reveals that even though Team Magma and Team Aqua have disbanded, a former Team Magma member--Brodie the Phantom Thief--is onboard and intent on stealing valuables.
When May goes to see the Ribbon Cup, Munchlax bumps the display case, breaking the Cup and revealing it's a fake. And without the Cup, the Grand Festival will be called off! Brodie must have stolen it, so a "Golden Pokeball" is put on display as a lure. Disguised as the Captain, Brodie distracts May and her friends and steals the Pokeball, but Officer Jenny had a tracking device installed in it and they set off in hot pursuit.
They chase Brodie through the ship, finally cornering him on deck. Brodie has now disguised himself as Officer Jenny and the only way to distinguish between the two is with Brock's keen eye for lovely ladies. Once his ruse is rumbled, he escapes and Team Rocket tries for the Ribbon Cup instead. But Ash and Officer Jenny are up to the job, and Team Rocket's plans are thwarted.