For what it's worth - and I'm sure I'll get flamed for this - legend tags are one of the few places I deliberately break the spec by leaving them out. I replace them with a heading of the appropriate level which provides the same information to the user but without the browser bugs.
(I'm happy to hear about the real-world downsides of this if anybody can see some)
edit: Oh and you should ask yourself why assistive technology users would want to hear the legends when your browser using users don't. If the answer is simply to satisfy the HTML specs, use display:none and be done with it - don't hinder the user experience of one group by providing useless information just for a formality.