Are you saying that the other mail server was deleted or the folder was deleted on the other server?
Does the folder show up in the Exchange Admin tool in the Public Folders folder, or only in Outlook (OE2000 = Outlook 2000?)?
If the other server no longer exists, then you essentially have an orphaned folder. By running the Consistency Checker, any orphaned objects would be re-homed to your server, which should then allow you to delete the folder (using the Exchange Administrator tool).
If the folder was just deleted on the other server, but the server still exists, you have a replication problem. Force replication again to see if that takes care of the problem. If the other server still exists but you have replication problems, you can still run Consistency Checker to re-home the folder.
However, Consistency Checker re-homes on an all or nothing basis. Therefore if there are other valid objects belonging to the other server, that have effectively been orphaned due to replication problems, runnign Consistency Checker could also re-home those objects to your server.
Hope this helps.