You have to talk to the Mole (and later, the Platypunk) in the first room of the arena (near the blue and red chests). I had beaten Captain Crow and his crew 3 times prior to beating the game, and I never found him again until I heard that you've gotta talk to these monsters to find him again.
For me, the mole first mentioned Captain Crow, I left and came back immediately and he congratulated me for beating him and gave me some prize. Left and came back again and the platypunk was there I believe, mentioned CC again.. and THEN I was able to fight him again.
4th fight - He sends a Marquis de Leon against you. 5th fight - Last fight with the captain, win and he joins you.
Don't forget to talk to the mole again after and he'll give you another reward.
Edit: Captain Crow appears at random whenever you enter a zone that is under adverse weather effects. Just keep going to the map screen and entering blinking zones until he shows up.
"I miss seeing Mario decapitate Sonic or Sonic peeing in Peaches *******. there's just no soul nowadays." - ShiNoBinn