Actually, the move tutor will teach a Pokémon any move that it could have known previously, not just moves that have been deleted. If you look at a Pokémon's move list, just take note of what level your Pokémon is at, and the move tutor will be able to teach your Pokémon any leveling-up move that it doesn't already know that it would learn naturally at a lower level then it currently is at. However, any moves that were learned by ways other than leveling up can't be relearned by using the move tutor.
