A nosotros nos pasaba lo mismo y era porque teniamos mal la MAC de destino, si al servidor le llega un paquete ICMP echo request (o cualquiera) y la MAC de destino no es la del servidor el paquete es descartado.
Por ejemplo: el cliente hace ping a un servidor, al router le llega un paquete IP que no es para ninguna de sus interfaces, decrementa el TTL, recalcula el checksum, la MAC de origen es la de la interfaz de salida con el prefijo mas largo, consulta la cache ARP y no tiene ninguna entrada para la IP del siguiente salto en la tabla de enrutamiento, entonces agrega el paquete a la cola y envia una consulta ARP, cuando el servidor responde se agrega a la cache y (supongo que es aqui cuando) a los paquetes que estan esperando en la cola se les agrega la MAC de destino, y se envian.