This problem existed for as long as tmpwatch was in RedHat distribution. The problem is that by default tmpwatch uses atime for both files and directories. But because tmpwatch is ran daily, the atime for directories is always <= 1day, so it never removes them... I believe that by default, tmpwatch should use atime for files and mtime for empty directories...
*** This bug has been marked as a duplicate of 14557 ***
Note: This is fixed in the rawhide and the beta trees.
I know this bug is ancient, but it never has seemed to work for me, even after the year 2000....