Sometimes I am asked to sign pseudonymous UIDs or see PGP keys which belong to organizations rather than single persons. These, by nature, do not contain the name of a real life person; hence there is no obvious way of verifying such identities. (One method I was offered was proving ownership of a domain related to the UID by making a signed document available on that domain, but I couldn't decide if this was enough.)
There are, however, reasons to include such keys (at least those of organizations) in the web of trust, for example a software release signing key should rather have some signatures on it. What would be a decent way of validating such identities (or: under which conditions could such an ID be declared as "verified")?