AlexeyVD

Поправьте меня, если я ошибаюсь, но разве данный запрос:

                    select -(`id`) from `dialogs` where # Получаем список диалогов
                        `deleted`='0' and # Не удалённых
                        `owner`='1' and # Основная запись
                        `id` in
                            (
                                select `id` from `dialogs` where # Диалоги
                                `user`=:u and # В которых я включен
                                `deleted`='0' # И из которых меня не удалили
                            )

не аналогичен такому:

                    select -(`id`) from `dialogs` where # Получаем список диалогов
                        `deleted`='0' and # Не удалённых
                        `owner`='1' and # Основная запись
                        `user`=:u  # В которых я включен

Вообще я бы переписал ваш вопрос как-то так (код примерный, у себя не тестировал):

SELECT COUNT(1)
  FROM
    (
      SELECT 1
        FROM messages m1
        WHERE m.to = :u
          AND m.deleted_to = '0'
          AND m1.unread = '1'
          AND m1.from != :u
      UNION ALL
      SELECT 1
        FROM messages m2
        JOIN dialogs d1 ON m.to = -(d1.id)
        WHERE d1.deleted = '0' 
          AND d1.owner = '1'
          AND d1.user = :u
          AND m2.unread = '1'
          AND m2.from != :u
    ) sel

Ну и не забывайте про соответствующие индексы.