Семёныч,

Придумать искусственную ситауцию, при которой такое может происходить - запросто.
К примеру, на одной из баз нет соответствующего индекса или статистика не собрана. Выполняется table scan вместо fetch по индексу. За определённое время доходит до нужной записи, для того, чтобы понять, что таких записей больше нет, надо досканировать таблицу до конца.

Каков сам запрос? Примерные размеры таблиц?
Что выдаёт
db2expln -database <dbname> -output exec_plan.txt -graph -opids -statement "<sql_statement>"
на одной и на другой базе?