I don't work there anymore, so I don't have access to the exact rule I used, but IIRC it was something like
iptables -t filter -I OUTPUT -d 169.254.169.254 -m owner \! --uid-owner 0 -j REJECT --reject-with icmp-admin-prohibited
iptables -t filter -I OUTPUT -d 169.254.169.254 -m owner \! --uid-owner 0 -j REJECT --reject-with icmp-admin-prohibited
Mind posting your entry for us iptables impared folks?