Sobre a pergunta do fim: se não me engano, quando o problema é o token o BadRequest vem com o fieldViolations apontando pro campo message.token. Se for outro campo, é payload, e eu nem contaria como falha do token. Esperar a segunda falha ajuda pouco, porque payload ruim falha igual toda vez.
No Unregistered do APNs eu usaria o timestamp antes de apagar. Se o app registrou o token de novo depois daquele horário, ele voltou a valer, e apagar seria perder um aparelho bom. Era a mesma regra que a Apple dava no antigo feedback service.