Una cosa, eso de que almacenan cartas hasta que haya una buena cantidad es MENTIRA, se acumula el correo económico (impresos y paquetes por superficie) pero las cartas salen todos los días.
No hablo por hablar, he trabajado en la terminal de carga de Correos en Barajas (CTI).
En teoría una carta a EEUU debería tardar unos 7-10 días y las europeas unos 3. Puedes poner la reclamación cuando quieras, aunque en Correos te dirán que es mejor que esperes a que pasen 30 días después de enviarla. La reclamación ponla por escrito en cualquier oficina de Correos mejor que por teléfono.
Y otra cosa, no envíes certificados urgentes al extrajero porque sólo te garantiza que sea tratado como urgente dentro del país de origen. Si quieres correo urgente internacional deberás usar EMS. También tienen un tipo de envío para Europa que llaman Correo Urgente Internacional pero no sé como funciona.