Replacing H1 text with a logo image: best method for SEO and accessibility?

If accessibility reasons is important then use the first variant (when customer want to see image without styles)

<div id="logo">
    <a href="">
        <img src="logo.png" alt="Stack Overflow" />
    </a>
</div>

No need to conform imaginary SEO requirements, because the HTML code above has correct structure and only you should decide does this suitable for you visitors.

Also you can use the variant with less HTML code

<h1 id="logo">
  <a href=""><span>Stack Overflow</span></a>
</h1>

/* position code, it may be absolute position or normal - depends on other parts of your site */
#logo {
  ...
}

#logo a {
   display:block;
   width: actual_image_width;
   height: actual_image_height;
   background: url(image.png) no-repeat left top;
}

/* for accessibility reasons - without styles variant*/
#logo a span {display: none}

Please note that I have removed all other CSS styles and hacks because they didn't correspond to the task. They may be usefull in particular cases only.

I do it mostly like the one above, but for accessibility reasons, I need to support the possibility of images being disabled in the browser. So, rather than indent the text from the link off the page, I cover it by absolutely positioning the <span> to the full width and height of the <a> and using z-index to place it above the link text in the stacking order.

The price is one empty <span>, but I'm willing to have it there for something as important as an <h1>.

<h1 id="logo">
  <a href="">Stack Overflow<span></span></a>
</h1>

#logo a {
   position:relative;
   display:block;
   width:[image width];
   height:[image height]; }

#logo a span {
   display:block;
   position:absolute;
   width:100%;
   height:100%;
   background:#ffffff url(image.png) no-repeat left top;
   z-index:100; /* Places <span> on top of <a> text */  }

You're missing the option:

<h1>
  <a href="http://stackoverflow.com">
    <img src="logo.png" alt="Stack Overflow" />
  </a>
</h1>

title in href and img to h1 is very, very important!