What size is your distribution database? How many packages and subscribers do you have? How long do you keep your history?

I found that in larger replication systems that the clean-up proces will actually time out because of the amount of data that is there and what the cleanup process is doing.