Да, в универсальном варианте придётся делать дополнительные расчёты: например, если не первая в столбце ячейка с rowspan="2" придётся высчитать для неё двух дополнительных соседей.
здесь это не важно, для универсального варианта придётся учесть

Так и знал что кто-нить использует пиксельный метод.
Главный минус его в том, что малейшее изменение стиля - и он перестанет работать.

Можно продемонстрировать на данном примере

Самое простое:

<style>
  table, td {border: solid 1px; cursor: pointer}
 *!* table{border-spacing:6px}*/!*
</style>
 
<table id="table">
    <tr>
        <td rowspan="3">0</td>
        <td>1</td>
        <td rowspan="3">2</td>
        <td colspan="2">3</td>
        <td>4</td>
    </tr>
    <tr>
        <td>5</td>
        <td  rowspan="2">6</td>
        <td>7</td>
        <td>8</td>
    </tr>
    <tr>
        <td id="td">9</td>
        <td>10</td>
        <td>11</td>
    </tr>
</table>​
 
<script>
window.onload = function () {//onload begin
  var table = document.getElementById('table');
  var coord, left, top, right, previous, next;
  var d = 5;//здесь можно уточнить
  var p, n;
 
  table.onclick = function(e) {//onclick begin
    e = e || event;
    var target = e.target || e.srcElement;
 
    if (target.parentNode.tagName == 'TR') {//if begin
      coord = target.getBoundingClientRect();
      left = coord.left + 1;
      top = coord.top + 1;
      right = coord.right;
      previous = document.elementFromPoint(left - d, top);
      next = document.elementFromPoint(right + d, top);
    
      if (previous.parentNode.tagName == 'TR')  {
        p = previous.innerHTML;
      } else {
        p = 'нет';
      }
 
       if (next.parentNode.tagName == 'TR')  {
         n = next.innerHTML;
       } else {
         n = 'нет';
       }
       
       alert('предыдущий: ' + p + '\nследующий: ' + n)
 
      }//if end
 
  }//onclick end
    
}//onload end
</script>

Я поэтому и закомментировал строчку (var d = 5;//здесь можно уточнить), имея в виду, что можно более точно рассчитать расстояние между ячейками (задача чётко попасть в ячейку, а не в промежуток между ними).
Допустим рассчитали, какие могут быть ещё варианты изменения стилей, чтобы скрипт потерял работоспособность?

Ну пиксельный имхо не АЙС, суть в том что Фактически, еще раз Фактичекси - все пикселы и координаты определяются столбцом и строкой якобы встроенных в ячейку - одного или нескольких ячеек с colspan и rowspan =1, поэтому на пикселы разменивацо смысла нет

координаты "Писксела" в таблице - есть координаты ячейки(столбец-строка) с размерами colspan-rowspan 1Х1 вписанного реального(если элемент соответствует 1Х1) или псевдо(если размеры больше) подобного элемента

И ширина - высота тоже в ячейках

Ячейки таблицы не такие уж и маленькие, чтобы в них не попасть.
Чем меньше размер ячейки, тем выше вероятность промаха, но вероятность того, что будут работать с чрезвычайно уменьшенной таблицей мала (естественно, данный способ не подходит для скрытых таблиц).
Если нужна абсолютная точность, можно подстраховаться, попиксельно (в смысле, увеличивая или уменьшая координату на 1) пройдя в цикле от самой ячейки до первой встретившейся (если такая есть) в нужном направлении.
Проще решения для произвольной таблицы с ячейками с rowspan и colspan, на мой взгляд, пока не видно.

bes,
я имхо не про размер -
Я про идеологию
Ну взять подложить под текущую таблицу такую же, но чисто с одно ячеистой структурой

Для огромных (как пишет ТС) таблиц хотелось бы более элегантного решения.
PS: я выше также предлагал выровнять структуру, что, кстати, наверное реально (пройтись по таблице и добавить недостающие ячейки с display: none).

А, кстати, это наверное неплохое решение, только проходя по таблице, добавлять не просто ячейки с display: none, а также и с соответствующим содержимым (тогда расчёт вообще простой).

bes,
Ну моё предложение прозвучало - проставить каждой ячейке индивидуальный класс
затем обойти и добавить классы соседских, добавляем только первый класс в списке, тады у нас классы всех сторон в атрибуте класс и поиск соседних перебором всех классов в текущей ячейке, нaчиная со второго в списке

Создание уникального класса элемента - номер строки + через букву номер столбца

Выяснить отсутствие соседей, зная класс текущего элемента и общее колво строк и столбцов и его соllspan, rowspan - тоже сложностей не представляет