Ran fsck (twice) till I got the message 'Macintosh HD volume is OK'. But the problems persist.

Also booted into OS 9 (after fsck), deleted some files and emptied trash, hoping that this would clean up the problem files. But when I booted back into OS X, trash was not empty.