O ICMP não é UDP e, na verdade, nem é IP. É outro protocolo da camada 3 OSI (camada de rede) ao lado do IP. Dito isso, ele tem um cabeçalho compatível com IP no início de um pacote.
Não há garantia de que um pacote ICMP será entregue. Ele tem as mesmas garantias de entrega de qualquer outro pacote na internet: nenhum. Não há tentativas de garantir que seja entregue, nenhum mecanismo de repetição, mas há uma soma de verificação no cabeçalho IP e no cabeçalho ICMP. Um protocolo de nível superior deve repetir o envio do pacote que gerou o erro, o que fará com que outro pacote de Tempo Excedido seja gerado e, eventualmente, um deles será recebido pelo remetente.
link tem um exemplo de cabeçalho ICMP (encapsulado dentro do que é idêntico a um cabeçalho IP) e informações sobre os diferentes tipos de mensagens ICMP.
Tendo em conta que as pessoas estão a votar neste post e a entender mal, vou esclarecer :
IP é a lingua franca da internet. Pacotes são roteados por seus cabeçalhos IP. Os protocolos são encapsulados em IP (TCP, UDP, SCTP, etc.) para a maioria das comunicações em nível de aplicativo.
Como você se comunica quando algo dá errado com a comunicação da camada IP? O ICMP é usado para isso. Você pode comunicar erros de camada IP em IP? É um problema de galinha e ovo, e como indicado por RFCs, fica lamacento. As mensagens ICMP têm um cabeçalho IP e um protocolo IP é reservado para elas, mas o ICMP é um protocolo de camada IP, não é encapsulado dentro de um pacote IP. Por isso, considero que seja um protocolo usado ao lado do IP.
Podemos criticar o dia inteiro como "se ICMP é IP", mas o máximo que eu admito é que sim, é IP, "mais ou menos".