Well, considering the semantics of the h-tags, it is not OK. Your headlines in the finished document should produce a document outline like
1. H1-Head
1.1 H2-Head
1.1.1 H3-Head
1.1.2 H3-Head
...
1.2 H2-Head
1.2.1 H3-Head
...
1.3 H2-Head
...
and so forth.
Of course this outline should conform the chronology of the tag occurences.
Update for your update
I would suggest the following markup
<h1><a>Main title of your site</a></h1>
<h2>Sidebar</h2>
<h3>Sidebar Headline 1</h3>
<h3>Sidebar Headline 2</h3>
....
<h2>Main content</h2>
<h3>Headline 1</h3>
<h3>Headline 2</h3>
...
Do you know the Firefox Web Developer Plugin? It has a function "Show document outline". There you can easily validate the logic of your markup. And to give you an idea, one good and one bad example from pfizer.com and phizer.de (I think you can get the idea, even if it is German - the headlines in red say "Missing Headline").
By the way: Having all that h-tags in your markup doesn't neccessarily mean that they all have to be visible ;-) !