Take a look at the 'Superflux' leds from Lumileds. These are not 5mm diameter devices, but they are a small 7.62mm square. There is a small dimple in the center of the device which acts as a lens.
These devices are _bright_. They are designed to efficiently carry heat away from the junction, and can be operated at 70mA. They are rated in lumen rather than candela, but the datasheet gives a conversion for the various beam angles offered.
The datasheet claims a typical luminous flux of 3500 mlm for red, and 4200 mlm for 'red/orange'. However when I ordered some of the 'red/orange' devices I got category 'J22' devices, which are rated for about 6000 mlm.
I ordered the wide angle LEDs, with a viewing angle of 70 degrees. According to the datasheet, these have a candela rating of about 3600 mCd. If I'd gotten the 'narrow' beam version, then the rating would have been something like 12000 mCd with a 30 degree beam.
-Jon