I had that same question a while back, some discussion on it in the first 3 posts of this thread.
For company sites I feel the the company name should really be the h1 on each page but its one of those things that can be argued every which way.
That's how I chose to handle the company name, in an h1 in the header.
Titles for sub pages then become h2 for me. I don't go for multiple h1 tags in a page even if html5 allows it.
In regards to your 2nd example. I would not put my logo in the list of links. It could limit the way you style your list and I feel it should be independent of the links. I've done them as background images on another anchor in the header before. That way it gives you a home page link from the logo. At the same time you can have a "home" link in your list.
Looking at your html examples again, I would definitely stay away from the 1st one. You would not want to nest your header in your nav. That would break the semantics of both of them. Then if your h1 was in the header it would wind up being a child of the nav. That would be confusing.
The 3rd example comes closest to what I'd do. I would place the company title in an h1, whether it has a link or not is up to you. I think a link in the logo is enough, people have come to expect a link in the logo.
In this markup below, the logo div can float left/right and then your h1 would slide up beside it
<div class="logo"><a href="#"></a></div>