[croikle]

> and I'm not entirely sure if those key-ID's are sufficiently unique and/or secure

They aren't: http://www.asheesh.org/note/debian/short-key-ids-are-bad-new...

[rlpb]

Short key IDs aren't. Just use longer ones. No format or protocol change is required.