Basically, the option for it to automatically remove songs when they're deleted requires specific preconditions...
That precondition
used to be 'Directory Cache' enabled, but it should now work, albeit slowly without it.
...I even tried deleting them in my ipods directory...
This may be part of the problem, as deleted files may be in the Recycle bin (perhaps even when RhythmBox deletes)?EDIT: That may not be relevant, as Linux does not have a recycle bin?
Try running the Disktidy plugin, that will empty the Recycle bin. Then do a Database Initialise and see what you get.
As a last resort, go into the .rockbox directory and delete all *.tcd files, which are all the database files and then re-initialise.
EDIT again: Sorry, I stupidly didn't realise the topic had been moved once, and I've gone and moved it again

* bascule should concentrate more on work than Rockbox