I'v encountered the same problems with a replication, When the publication was removed it didnt get totally deleted from the publication server. It all happend some time ago so I don't quite know anymore how I solved it, but I do remember that it made a difference how I removed the publication: by unchecking the database in published databases via the tools menu, or by removing the publication in the Replication tree from Enterprise manager

I think it is a glitch in SQL ...