1. Temporary names and categories grouping by observed properties
If not every detail of a multiverse item is known, then it's logically impossible to know exactly which universe you're in. As an extension of that, you're probably not going to be able to give one a unique, descriptive name to any given universe. But if multiverse monikers have something like a hashed name representing different features, perhaps organized from general things (like fundamental rules of physics) to specific things (like names of villages at distinct points in time), a name can categorize which broad "group" of universe you're in.
Critically, if universes are fractally detailed and your ability to observe all of their details is limited, then there is going to be a maximum level of precision which you can apply to identifying them-- you'll never be able to fully specify even one, let alone all of them together.
2. A function which takes information about a universe as inputs
If the agency has some protocol for observing, classifying, and identifying universes, the idea of a specific name for a universe may not be necessary. You feed observations into the function, and it tells you "where" you are. Depending on how exactly your travelling between universes works, it may not be feasible to say "I want to go to Universe 8213213246HSXIAZ"-- it may be the best you can do to simply identify where you happen to be, and compare that to records other travelers have left.
3. It's a work in progress, and always will be
If the possibilities are literally endless, and the level of detail distinguishing universes from one another is effectively infinitely, fractally complex, then the idea of constructing a complete catalog is probably not what this agency would have in mind. Instead they'll get to work, knowing that their labors will never end, and updating their classification schemes at need (instead of trying to account for infinite possibilities at the outset).
4. Names are arbitrary, if you can't tell the difference universes might be the same, and the agency started somewhere
The agency starts in one universe (well, infinite universes), and coordination will not be possible across all analogous agencies (since infinite instances of the agency will also mean infinite, arbitrarily different naming and classification approaches). So each agency might as well just start numbering the universes they encounter, labeling their own universe as Universe 1 (or Universe A).
This idea reminds me of the old TV show Sliders, where arbitrary "coordinates" were (eventually) assigned to parallel universes with infinite possible variations. The information wasn't part of a generally accessible catalog, it was strictly a reference for specific travelers.
5. Close enough!
There is a philosophical approach suggesting that, if two things do not differ in any of their properties, then they are the same thing. If the ability of your agency to observe the details of universes is limited, either practically (there are so many new kings to memorize) or inherently (some details simply cannot be observed, because they lack the technology or something), then the agency's ability to state that they are in a new universe is limited.
The effective set of universes it can observe, document, and name is going to be limited. There will be many universes (well, infinite universes) which the agency just can't distinguish between. It may be aware of this, and respond as in (1), or they may not, and they will call many, many universes by the same name out of ignorance. Either way, it really cuts down on the complexity of the task of cataloging them, though infinite universes will still present infinite challenges and infinite work.