Based on my own experience, I’ve used a combination of method 1 & 2 – the architecture and footer scripts of 1, and the ‘look-ahead’ technique of 2.
For the look-ahead though, I use regex in place of stripos; personal preference, faster, and can check for ‘malformed’ shortcode;
preg_match( '#\[ *shortcode([^\]])*\]#i', $content );
If you’re concerned about authors using do_shortcode manually, I would opt to instruct them to use an action call enqueue your pre-registered style manually.
UPDATE: For the lazy author who never RTFM, output a message to highlight the error of their ways 😉
function my_shortcode()
{
static $enqueued;
if ( ! isset( $enqueued ) )
$enqueued = wp_style_is( 'my_style', 'done' ); // cache it so we don't repeat if called over and over
// do shortcode
$output="";
if ( ! $enqueued )
// you can output the message on first occurence only by wrapping it in the previous if
$output .= <<<HTML
<p>Attention! You must enqueue the shortcode stylesheet yourself if calling <code>do_shortcode()</code> directly!</p>
<p>Use <code>wp_enqueue_style( 'my_style' );</code> before your <code>get_header()</code> call inside your template.</p>
HTML;
return $output;
}