Всем спасибо за обсуждение. Почитав участников я понял, что задача в полной мере нереализуема, полностью индексированный доступ неосуществим. Вариант с UNION ALL мне тоже приходил в голову, но это будет работать только если параметр приоретизации идет первым или последним. В итоге решено сделать выборку как есть. Оценки дают максимальное количество в очереди порядка 20к, так что надюсь потянет. Если будет неудовлетворительно, то будем убеждать заказчика отказаться от проблемных параметров.

Кстати, а сортировка будет оптимизирована, если индекс есть по нескольким первым ключам? будет ли он эффективен или все свалится в Full table scan?