Handling held messages on large installations is very slow

On an avg, handling a single held message on mail.python.org takes ~2 seconds, which is quite slow. Debugging the issue further made me realize that the code scales linearly and can be slowed down by excessive held message on other lists.