Assuming this is still desirable I'd really like to move forward with this issue.
The current situation is that we have two patches.

My patch
========

pros: 
 * affects asyncore.py only
 * (imho) cleaner, as it just adds one class
 * stable, as it has been used in pyftpdlib for over 3 years now

cons:
 * significantly slower compared to Josiah's "paired-heap" approach 


Josiah's patch
==============

pros:
 * significantly faster

cons:
 * affects asyncore.py and sched.py
 * sched.py is modified quite heavily, also it's not clear whether that has been done in a fully retro-compatible way or not, so a full review from someone who has experience with this module would be needed
 * it seems that sched.py gains brand new functionnalities which are not necessarily related with asyncore, hence tests and documentation should be added. Furthermore, belonging them to sched.py, maybe they should be treated in a separate issue


Both patches should no longer apply cleanly so they should be adjusted a little and the missing parts (full tests, documentation including example usage, etc...) completed.
It seems we both agree on the API, which is both simple and has the extra advantage of being the same as Twisted's.
Now it's only a matter of deciding what to do about the internal implementation.