Still, some middlebox/stateful firewall/etc. messing with 169.0.0.0/8 is plausible.
My answer was "some network admin is having fun with a middleware box", you will have to speak with them. They did, and the response that came back is "we are moving to a network with real security". Access was restored. It was a Palo Alto NGFW as others have mentioned.
IMHO the industry looking for way to move high priced gear, and they convince someone with a sparrow problem with barely knows how to handle an air rifle to buy bazooka's. A bit of collateral damage is to be expected....
EDIT - I've now scrolled down in HN and saw that this was ruled out.
BTW your assumption "a successful ICMP ping = TCP and UDP work" is an extremely common one that I too had before I was taught otherwise.
I did not assume. The comment to which I was responding suggested it was the destination IP that was the problem. Generally (but not always) an IP filter would be applied irrespective of protocol. I also pointed out that the initial SYN and reply SYN/ACK are getting through the hypothesized bogon filter and those are part of TCP. I don't think the bogon filter is a hypothesis that fits the evidence.
ETA: but adding connection state tracking + a filter does make sense https://news.ycombinator.com/item?id=39822214
I've never seen this (all protocols by default) in any environment I've personally worked with, but perhaps I've had a unique experience.
Are you referring to local networks only?
It's very common to not allow ICMP by defaul to workloads in the cloud, e.g. in AWS.
Edit: here's a good page about the effects of disabling ICMP: https://www.rimscout.com/why-you-should-not-block-icmp/
Also there's some blackhole detection or how is it called.
However it's OK to block _parts_ of the ICMP protocol for security reasons, like echo and reply.
I once was a customer of an ISP that mistakenly blocked the whole 192.0.0.0/8 net, which caused some confusion, but they fixed it after I pointed it out.