Hi John,
Do you have any predicates in your selector that only looks for Ads that are either Active or Paused, not Disabled/Removed? If you don't, please add them and see if you are still getting the deleted Ad.
If you do, can you please send me your SOAP request and response for this call using Reply privately to author?
Thanks,
Anthony
AdWords API Team