Use adsiedit.msc to manually remove the Public Folders:
Open Adsiedit.msc from run command
Connect to your server (right-click on ADSI Edit, then Connect). Select Configuration for the well known Naming Context
Expand to CN=Services/CN=Microsoft Exchange/CN=your organization name/CN=Administrative Groups/CN=Exchange Administrative Group/CN=Servers/CN=Your MailBox Server. Expand it and then locate Information Store.
Locate particular storage group where is Public Folder Store. On the right pane, delete the public folder store (storage group).
Best Answer
Not cleanly. You can go thru the tedious How to remove Exchange Server 2003 from your computer procedure. I wouldn't recommend doing that, if at all possible.
If you're not in a hurry, consider getting your hands on a copy of the CD and doing the uninstall that way.