Check the markings on different electrical boxes. According to the National Electrical Code (NEC) (which is not applicable in all areas, so check local codes), boxes that support ceiling fans should be listed for the purpose.
National Electrical Code 2008
ARTICLE 314 Outlet, Device, Pull, and Junction Boxes; Conduit Bodies; Fittings; and Handhole Enclosures
314.27 Outlet Boxes.
(D) Boxes at Ceiling-Suspended (Paddle) Fan Outlets. Outlet boxes or outlet box systems used as the sole support of a ceiling-suspended (paddle) fan shall be listed, shall be marked by their manufacturer as suitable for this purpose, and shall not support ceiling-suspended (paddle) fans that weigh more than 32 kg (70 lb). For outlet boxes or outlet box systems designed to support ceiling-suspended (paddle) fans that weigh more than 16 kg (35 lb), the required marking shall include the maximum weight to be supported.
A box like this 4 in. Octagon Box, is rated to hold 50lbs, however, that's only when it's properly installed. Since it sounds like you don't have much room to work, you'll probably have difficulty installing it properly.
You're obviously not going to want to use a box like this Ceiling Box, which only attaches to the drywall.
The best choice in this situation is a box supported by a brace.
I'm not sure what you meant when you said "The remodeling-type expander brace failed", but not all braces are created equal so it may be worth a second try. With this Westinghouse Saf-T-Brace (and others), installation is fairly easy even when you're working through a small 4" hole.
- Remove the electrical box and saddle from the brace (if it's not already).
- Slip the brace up into the ceiling, and rest the "legs" on the drywall.
- Using an adjustable spanner or open ended wrench, rotate the center part of the brace. This will cause the ends to expand outward toward the joists. Continue until the brace is firmly in place.
- Slip the saddle back over the brace.
- Affix the cable to the box, and mount the box to the saddle.