CentOS yum thinks removed packages are still installed

I have 2 packages in my yum that I would like to get rid of. When I list the installed packages they appear in the output, and when I try to erase them, yum seems to think it's ok and proceeds with the removal. However, they never go away, they stay in the list and I can erase them 42 times and nothing happens. There is no error message. I've tried rebuilding the rpm database with:

rm -rf /var/lib/rpm/__db.00*
rpm –rebuilddb

And that didn't help. Example:

$ yum erase eclipse-ecj.x86_64
Loaded plugins: fastestmirror
Setting up Remove Process
Resolving Dependencies
--> Running transaction check
---> Package eclipse-ecj.x86_64 1:3.2.1-19.el5.centos set to be erased
--> Finished Dependency Resolution

Dependencies Resolved

=====================================================================================================
 Package               Arch             Version                            Repository           Size
=====================================================================================================
Removing:
 eclipse-ecj           x86_64           1:3.2.1-19.el5.centos              installed            23 M

Transaction Summary
=====================================================================================================
Remove        1 Package(s)
Reinstall     0 Package(s)
Downgrade     0 Package(s)

Is this ok [y/N]: y
Downloading Packages:
Running rpm_check_debug
Running Transaction Test
Finished Transaction Test
Transaction Test Succeeded
Running Transaction
  Erasing        : eclipse-ecj                                                                   1/1

Removed:
  eclipse-ecj.x86_64 1:3.2.1-19.el5.centos

Complete!
$ yum erase eclipse-ecj.x86_64
Loaded plugins: fastestmirror
Setting up Remove Process
Resolving Dependencies
--> Running transaction check
---> Package eclipse-ecj.x86_64 1:3.2.1-19.el5.centos set to be erased
--> Finished Dependency Resolution

Dependencies Resolved

=====================================================================================================
 Package               Arch             Version                            Repository           Size
=====================================================================================================
Removing:
 eclipse-ecj           x86_64           1:3.2.1-19.el5.centos              installed            23 M

Transaction Summary
=====================================================================================================
Remove        1 Package(s)
Reinstall     0 Package(s)
Downgrade     0 Package(s)

Is this ok [y/N]:

Help!