With the help of AaronCampbell, the shortcode HTML issues have been fixed in a flexible way. Now add_shortcode() takes a third (optional) parameter that allows you to have your shortcode be expanded after wpautop() and texturize() are run. Default is before for compatibility with 2.5. For “block-level” shortcodes, you should probably make them run after. For “inline” shortcodes, you should probably make them run before.
Update: We went a different way with this, for the time being. Now everything runs at 11, but shortcodes with a buffer line separating them from other content will be recognized as block level and won’t get paragraph-wrapped.