Иван

Правильно ли я понимаю, что база данных для вас - просто хранилище настроек?..

Загружайте все себе в память, и кладите в хеш-таблицу. Если особенно нужна скорость - можно использовать идеальный хеш (т.е. подобрать параметры хеш-функции таким образом, чтобы в таблице не было коллизий). После этого пропадет еще и необходимость очереди - ну или в очередь будут попадать уже отфильтрованные пакеты.

Обновлять данные либо периодически подгружая их из базы, либо по "пинку" из триггера. При обновлении данных лучше всего сначала построить новую хеш-таблицу, а потом ее атомарно заменить - это позволит строить новую таблицу без ограничения по времени.

Использовать локальный кэш тоже не очень хороший вариант, т.к. в БД могут писать их других мест, а данные нужны актуальные.

Использовать локальный кеш. Обновляются данные явно не каждые 1мс, за которые вы боретесь.
Обновление - вплоть до из триггера пинать UDF, которая сообщит вашему приложению, что данные в БД обновились.

Пример запроса хотелось'б видеть, может есть что оптимизировать?
Индексы созданы?

Прибывали обратится напрямую к хранилищу через интерфейс memcached?
mysqld_plugin_memcached + отключенные транзакции.