Понял свою ошибку.
Вот листинг работающего примера (с исп. RegExp):
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<title>Untitled</title>
<script language="JavaScript">
function sort_table()
{
var pattern_string = '';
var counter = 1;
if (document.test_form.filter.value != '')
pattern_string = '^' + document.test_form.filter.value;
while (counter <= 6)
{
var element = document.getElementById('td_' + counter);
if ( (element.innerHTML.search(pattern_string) != -1) || (document.test_form.filter.value == '') )
element.parentNode.style.display = '';
else
element.parentNode.style.display = 'none';
counter++;
}
}
</script>
</head>
<body>
<table id ="test_table" width="100%" border="1">
<tr id="tr_1"><td id="td_1">111</td></tr>
<tr id="tr_2"><td id="td_2">222</td></tr>
<tr id="tr_3"><td id="td_3">333</td></tr>
<tr id="tr_4"><td id="td_4">444</td></tr>
<tr id="tr_5"><td id="td_5">555</td></tr>
<tr id="tr_6"><td id="td_6">123</td></tr>
</table>
<p>
<form name="test_form" method="get" action="#">
<input name="filter" type="Text" onkeyup="sort_table()" value="">
</form>
</p>
</body>
</html>