Several months ago a large number of pets got lost. A fix was put in place that restored pets from backup automatically when the owner logs on. After the upcoming patch this automatic restore has to be disabled, so make sure you log in all your characters at least once to ensure all your pets are restored.
Daan
Save your Pets! Old Unused Characters and the Patch
Moderator: Caretakers