Otimização de Indexação Simples

Conforme explicado no comentário acima, o INDEX(Dob) não é usado -- já que este é um índice em ano-mês-dia . Você precisa criar um índice em mês-dia .

Provavelmente não é a solução mais elegante, mas:

CREATE TABLE `birthdayCard`(`Email` VARCHAR(255), `FirstName` CHAR(30), `LastName` CHAR(30),
                            `Mob` int, `Dob` int, 
                            PRIMARY KEY (Email), INDEX(`Mob`, `Dob`));

Consulte http://sqlfiddle.com/#!2/db82ff/1

Para uma resposta melhor( ?):como o MySQL não suporta colunas computadas, você pode precisar de gatilhos para preencher colunas "mês-dia" e ter um índice nela:

CREATE TABLE `birthdayCard`(`Email` VARCHAR(255), `FirstName` CHAR(30), `LastName` CHAR(30),
                            `Dob` DATE,
                            `Birthday` CHAR(5),
                            PRIMARY KEY (Email), INDEX(`Birthday`));

CREATE TRIGGER ins_bithdayCard BEFORE INSERT ON `birthdayCard`
FOR EACH ROW
    SET NEW.`birthday` = DATE_FORMAT(NEW.`Dob`, "%m%d");

CREATE TRIGGER upd_bithdayCard BEFORE UPDATE ON `birthdayCard`
FOR EACH ROW
    SET NEW.`birthday` = DATE_FORMAT(NEW.`Dob`, "%m%d");

Isso permite inserções "simples", preservando se necessário o Dob completo como no seu exemplo original:

insert into birthdayCard (Email, FirstName, LastNAme, Dob) 
   values ("[email protected]", "Sylvain", "Leroux", '2013-08-05');

O SELECT query deve ser modificada para usar a nova coluna "search":

SELECT * FROM `birthdayCard` WHERE Birthday = DATE_FORMAT(NOW(), "%m%d");

Defina http://sqlfiddle.com/#!2/66111/3