When Shadow leaves your party for the first time is random. He will either leave at the Phantom Forest, or just before the Waterfall. He returns much later on in the game. I can't remember if he levels between then, but I think it might do. Side note: If you want Shadow in your party in the second half of the game, wait until about five seconds before the timer runs out on the floating continent. I.e. Don't jump on the airship until he turns up. Just hang on, he will come.