you can try some of http://www.viaembedded.com
boards, mini-itx (17x17cm) or nano-itx (12x12cm), just recently released.
However - we have used mini-itx M10K version, but departured with it, because of its instability some two years ago. It is VERY sensitive to the model of RAM you put into it.
Situation might change though. And what is more, there is now more companies, developing mini-itx boards, even Pentium-M based, e.g. Commell.
Some links to try:
You can build really small, much more powerfull router than RB500 is, however forget PoE for e.g., and it will surely cost you more ...