どこにも関連付けてないはずのEIPなのに解放しようとすると

123.345.567.789: The address with allocation id [eip-0123456789abcdefg] cannot be released because it is locked to your account. Please contact AWS Support to unlock it.
Service: AmazonEC2; Status Code: 400; Error Code: InvalidAddress.Locked; Request ID: 12345678-9ab-cdef-ghij-klmnopqrstuv)

みたいなことを言われて失敗することがあります。

今回がまさにそうだったんですが、EIPを関連付けたEC2からメール送信を行う等の理由でIPアドレスの逆引き設定をしてもらっている場合などが該当します。

この逆引き設定がされているかどうかはお手元のコンソールから確認することができます。

$ host 123.345.567.789
123.345.567.789.in-addr.arpa domain name pointer sample.example.com.

こんな感じなら逆引き設定されているということになります。

この場合はAWSの専用サポートのUse Caseに「rDNSを削除してちょ」って書くと削除してもらえます。

Please remove following rDNS lookup settings:
789.567.345.123.in-addr.arpa domain name pointer sample.example.com.

逆引きが設定されていない、または設定が削除されたかどうかも同じくお手元のコンソールから確認できます。

$ host 123.345.567.789
789.567.345.123.in-addr.arpa domain name pointer ec2-123-345-567-789.ap-northeast-1.compute.amazonaws.com.

こんな感じになってれば逆引き設定がされていない状態なのでEIPも解放できると思います。