Хоть я и не мастак верстки, но элегантное кросс решение все же сделал =)

увы… Да.

Попросили вылижить мое решение. Решение элегантное потому что таблица становится не такой как ее привыкли видеть

П.С. могут быть проблемы в ИЕ6. А так решение кроссбраузерное вроде.
Недостаток: Столбцы заголовка по центру без JS не выровнять.Зато плюс большой: как не крути размеры .block таблица выглядит нормально, если конечно размеры не меньше минимальной ширины заголовка. Тогда заголовок вылезает заширину таблицы

<style type='text/css'>
.block {
  width:80%;
  height: 100px;
  position: absolute;
  top: 20px;
  overflow: visible;
  }
.scroll {
  width: 100%;
  height: 100%;
  overflow: auto;
  }
.head.fixed {
  height: 20px;
  top: -20px;
  position: absolute;
  background: LemonChiffon;
  border-bottom: 1px solid black;
  width: 100%;
  }
.table {
  border-collapse: collapse;
  }
.table td { border: 1px solid gray; border-top: 0px;}
tr.head td {  height:0; } 
tr.head td .st {
  white-space: nowrap;
  position: absolute; 
  top: -20px;
  height: 20px;
  border-left: 1px solid gray;
  line-height: 20px;
  padding-left: 10px;
  margin-left: -1px;
  }
tr.head td .or { white-space: nowrap; height:0; overflow: hidden; padding-left: 10px;}
</style>

<div class='block'>
<div class="scroll">

<div class="head fixed"></div>

<table cellpadding="0" cellspacing="0" class="table">
  <tr class='head'>
    <td width="100"><div class='st'>Столб</div><div class='or'>Столб</div></td>  <!-- должны быть одинаковые значениея для авто подгонки столбцов по заголовкам -->
    <td><div class='st'>Столбец 2 длинный</div><div class='or'>Столбец 2 длинный</div></td>
    <td><div class='st'>Столбец 3 очень длинный </div><div class='or'>Столбец 3 очень длинный</div></td>
  </tr>
  <tr>
    <td>Жили были дед да бабка был у них колобок. А также дед еще рыбку золотую любил ловить</td>
    <td></td>
    <td>Жили были дед да бабка был у них колобок. А также дед еще рыбку золотую любил ловить</td>
  </tr>
  <tr>
    <td>Жили были дед да бабка был у них колобок. А также дед еще рыбку золотую любил ловить</td>
    <td></td>
    <td>Жили были дед да бабка был у них колобок. А также дед еще рыбку золотую любил ловить</td>
  </tr>
  <tr>
    <td>Жили были дед да бабка был у них колобок. А также дед еще рыбку золотую любил ловить</td>
    <td></td>
    <td>Жили были дед да бабка был у них колобок. А также дед еще рыбку золотую любил ловить</td>
  </tr>
  <tr>
    <td>Жили были дед да бабка был у них колобок. А также дед еще рыбку золотую любил ловить</td>
    <td></td>
    <td>Жили были дед да бабка был у них колобок. А также дед еще рыбку золотую любил ловить</td>
  </tr>
  <tr>
    <td>Жили были дед да бабка был у них колобок. А также дед еще рыбку золотую любил ловить</td>
    <td></td>
    <td>Жили были дед да бабка был у них колобок. А также дед еще рыбку золотую любил ловить</td>
  </tr>
  <tr>
    <td>Жили были дед да бабка был у них колобок. А также дед еще рыбку золотую любил ловить</td>
    <td></td>
    <td>Жили были дед да бабка был у них колобок. А также дед еще рыбку золотую любил ловить</td>
  </tr>
</table>

</div>
</div>

дубль

Вообще, можно джаваскриптом решить достаточно просто. Нужно лишь посчитать ширину столбцов таблицы и потом применить это к заголовку. Рабочий пример - фиксированный заголовок таблицы