What kind of entry are we talking? a machine that WAS on your network that's been removed? or something else? What kind of record is it?
Out of curiousity, if it's a record from an old workstation, check under the AD users and computers snap in and make sure the old computer account was removed.
~ K.I.S.S - Don't make it any more complex than it has to be ~