wildcard not working after record deleted

[Maria Iano]

We have a group of users that need to use a wildcard record in their
zone. Their wildcard works in general, but they have a situation where it
isn't working. They had some records that they deleted, and expected
the wildcard to take over, but it hasn't. If we query a record that
doesn't exist and never has in the zone, then we get the answer from
the wildcard. If we query a record that used to exist but was deleted
and now doesn't exist, then we get no answer. We don't get NXDOMAIN, we
get

status: NOERROR

and no answer.

Has anyone else come across this?

Thanks,
Maria