Thanks for the suggestion to split up the primary key into components. But even going down this way, packing the components into one superstructure (composite type) would be beneficial as the same scheme is used across multiple tables. And we are back at the original problem.
This is probably a completely naive question, but why not store this in a text field?