Aunque un comentario de Gayot lo explica en su mayor parte, he pensado en ampliar y añadir mi experiencia.
Para otros visados, también he tenido que explicar mis viajes anteriores. Viajo mucho (más hace unos años, pero sigo intentándolo), y como has comprobado, no todos los sellos de los pasaportes son claros, ni visibles, y francamente, ¡algunos países ni siquiera los sellan!
Si utilizas gmail, o cualquier otro servicio de correo electrónico en el que archives tus correos, esto me resultó muy útil para la búsqueda: escribía el nombre de un país en la búsqueda de mi bandeja de entrada y a menudo aparecían discusiones, chats, correos electrónicos o reservas que lo indicaban.
Como un geek, también ejecuto Google Latitude (ahora parte de Google+) que rastrea mi historial de ubicación - he sido capaz de usar eso para averiguar dónde estaba (o cuando estaba en el día x).
Otra opción si llevas tiempo en una empresa es preguntar a RRHH, puede que tengan un registro de tus bajas en los últimos x años, y eso también puede ayudar a acotar.
Por último, como dijo Gayot, añada una nota explicando que las fechas son una suposición del mejor esfuerzo, de todas esas fuentes. En mi experiencia, los países suelen ser más importantes que las fechas.
