Inode Usage

Inode usage on one of my servers is up to 85%

Whats the best way of finding which directories are storing loads of files?

df -i

is your friend here. locate the higher counter file systems and then try looking into deeper level.