문서에 보시면 registrationId가 삭제될 때까지는 어느 정도 시간이 소요될 수 있다고 명시하고 있습니다.
"Note that it might take a while for the registration ID be completely removed from GCM. Thus it is possible that messages sent during step 7 above gets a valid message ID as response, even though the message will not be delivered to the device."