I have had similar problems on a sql2k replication subsystem. Removal of subscriptions from a publication deadlocked+killed, leaving orphaned subscriber info on the distributor.

Replication monitor reports the subscription from distribution database, but publication does not think there are any (until an error is thrown when attempting to delete).

Recreating the subscriber completed ok, but when attempting to delete the new the publication again the new subscription info was removed & an error thrown at the orphaned data again.

To resolve, I went to the distribution database on the distributor & checked for the relevant subscriber in mssubscriptions & found the article data from msarticles

this allowed me to successfully use sp_msdrop_subscription to remove the orphaned data.

After that removal of the publication was ok.