А запросы выполняются на одном и том же сервере с теми же параметрами? Не верю.
Bookmark lookup происходит, например, когда отбираются записи из некой таблицы по индексу с проверкой каких-нибудь условий, а потом нужно извлечь другие поля из этой таблицы, которых нет в индексе или проверить какие-то другие условия. Тогда при первом отборе "выдергиваются" id записей (создаются букмарки), а потом по ним идет обращение непосредственно к записям в этой таблице. Избавиться можно созданием составного индекса по всем полям, по которым идет выборка из таблицы. Но плодить много индексов на таблицу, данные в которой часто изменяются, не следует...