ICMP is not UDP, and it's actually not even IP. It's another OSI layer 3 protocol (network layer) alongside IP. That said, it has an IP compatible header at the beginning of a packet.
There is no guarantee that an ICMP packet will be delivered. It has the same delivery guarantees of any other packet on the internet: none. There are no attempts to ensure that it gets delivered, no retry mechanism, but there is a checksum in both the IP header and the ICMP header. A higher level protocol should retry sending the packet that generated the error, which will cause another Time Exceeded packet to be generated, and eventually one of these will be received by the sender.
http://www.networksorcery.com/enp/protocol/icmp.htm has an example ICMP header (encapsulated inside what is identical to an IP header) and information about the different types of ICMP messages.
Given that people are downvoting this post and misunderstanding, I'll clarify:
IP is the lingua franca of the internet. Packets are routed by their IP headers. Protocols are encapsulated within IP (TCP, UDP, SCTP, etc) for most application level communication.
How do you communicate when something goes wrong with IP layer communication? ICMP is used for this. Can you communicate IP layer errors in IP? It's a chicken and egg problem, and as indicated by RFCs, gets muddy. ICMP messages have an IP header, and an IP protocol is reserved for them, but ICMP is an IP layer protocol, not it is not encapsulated inside an IP packet. Therefore I consider it to be a protocol used alongside IP.
We can quibble all day long as to "whether ICMP is IP", but the most I'd concede is that yeah, it's IP, "sort of".