What do they get paid to do? What do you evaluate them on come review time?

As long as you are paying them to resolve problems, cleaning will always be a low priority. If you really want their areas cleaned then base their reviews on tidyness not on productivity.