If an oracle client isn’t able to resolve client hostname, throws an
ORA-21561: OID generation failed

On log/listener.log I found
20-MAR-2013 16:15:30 * (CONNECT_DATA=(SID=test)(CID=(PROGRAM=perl@foo.example.com)(HOST=foo.example.com)(USER=bar))) * (ADDRESS=(PROTOCOL=tcp)(HOST=192.168.0.139)(PORT=48363))

The client hostname was managed via DHCP, so the hostname wasn’t in /etc/hosts.

The root cause of the issue was a slow DNS response – so adding the client hostname on the client machine fixed the issue.