Каюсь, схалтурил (извините). Можно так:

var uls = document.getElementsByTagName('ul');
for (var i=uls.length-1; i>=0; i--) {
  if (uls[i].innerHTML.search(/<li.*>/i) == -1)
    uls[i].parentNode.removeChild(uls[i]);

Проверил, вроде работает.

Дополнение:
В любом случае, мне кажется со строкой быстрее будет чем с домом, хотя нагрузочного тестирования не проводил.

Не надо портить код ради преждевременной оптимизации. Это место в любом случае тормозить не будет.

Почему "портить код"? Что в нем испорченного?
Мне кажется, просто дело привычки. Т.е. мне привычнее обрабатывать через innerHTML, Вам через DOM. Разве это говорит, что код испорчен?

Я тоже безмерно люблю innerHTML, но когда вопрос стоит "сколько тегов есть в таком-то теге", то это, разумеется, getElementsByTagName. Тут по названию метода ясно, что мы делаем, в случае же innerHTML -- из знания регулярных выражений, которые зачастую мало читабельные.

Не испорчен, конечно, просто менее читабелен.