¿Cómo validar si múltiples registros existen en una tabla?

[esneideramy]

¡Hola! Soy nuevo en el foro, por lo tanto pido disculpas si algo de mi pregunta les pueda incomodar. antes que nada quiero que tengan en cuenta que ya busqué en Google posibles soluciones a mi pregunta, pero nada he podido solucionar, así que probaré si aquí llego a una solución exitosa con ayuda de ustedes.

Pasa lo siguiente: tengo una tabla en MySQL en la que guardo el historial de conexión de mis usuarios, asgo así:

_______________________________________
............. connectionhistory.................|
_______________________________________
userId.........|..........Date.................... |
______________________________________|
337.............| 2013-08-16 16:42:52 |
337.............| 2013-08-17 16:42:52 |
338.............| 2013-08-18 16:42:52 |
339.............| 2013-08-18 16:42:52 |
340.............| 2013-08-18 16:42:52 |
______________________________________|


Quiero obtener toda la información que haya en un rango de fecha por ejemplo:

Código MySQL:

SELECT * FROM connectionhistory
WHERE Date >= '2013-08-17 16:42:52' 
AND Date <= '2013-08-18 16:42:52'
 

ésta consulta me devolvería:
337 | 2013-08-17 16:42:52 |
338 | 2013-08-18 16:42:52 |
339 | 2013-08-18 16:42:52 |
340 | 2013-08-18 16:42:52 |

Ahora, lo que quiero hacer es un poco mas complejo: quiero que solo me retorne éstos datos, en el mismo rango de fecha, pero que no me retorne una fila, si su userId ya se encuentra registrado en una fecha anterior a la fecha menor (inicial) de mi consulta.

he intentado lo siguiente:

Código MySQL:

SELECT DISTINCT @usr:=userId, Date FROM connectionhistory
WHERE not EXISTS (SELECT userId FROM connectionhistory
                                WHERE usrID = @usr 
                                AND  Date < '2013-08-17 16:42:52')
AND Date >= '2013-08-17 16:42:52' 
AND Date <= '2013-08-18 16:42:52';
 

Necesito que me retorne lo siguiente:
338 | 2013-08-18 16:42:52 |
339 | 2013-08-18 16:42:52 |
340 | 2013-08-18 16:42:52 |

ya que el userId = 337, ya se encontraba registrado en la tabla, en una fecha anterior a: 2013-08-17 16:42:52, la cual es la fecha inicial de mi rango de consulta.

como nota final, mi deseo es hacer esto en una consulta o procedimiento almacenado en MySQL, se que podría obtener los datos del rango de fecha, y luego (con php) comprobar si cada uno de los userId se encuentran en la tabla en una fecha anterior a la del rango que deseo