Actually, the interesting part is that he starts with a main verb, then goes on to list locatives that apparently apply to the previously stated verb, suggesting that this must be poetry, since it defies all norms for Klingon grammar.

Oh come on! It's perfectly grammatical. Trim off the extraneous loS:

qIb HeHDaq on the edge of the galaxy

'u' SepmeyDaq Sovbe'lu'bogh to unknown regions of the universe

lenglu'meH He ghoSlu'bogh retlhDaq beside a way one follows in order that one travels

'oHtaH it is

This is a "to be" sentence with a long, nested locative and a shorter locative.

The first locative is qIb HeHDaq. This specifies the location of Deep Space 9.

The next locative is 'u' SepmeyDaq Sovbe'lu'bogh lenglu'meH He ghoSlu'bogh retlhDaq beside a passage to unknown regions of the universe.

Start with a noun:
retlhDaq beside (simple locative)
Now look at a noun phrase: He ghoSlu'bogh way which one follows
Add a purpose clause to this phrase: lenglu'meH He ghoSlu'bogh way which one follows in order to travel
Now invent a destination: 'u' SepmeyDaq Sovbe'lu'bogh to unknown regions of the universe
Put this destination on the traveling: 'u' SepmeyDaq Sovbe'lu'bogh lenglu'meH He ghoSlu'bogh way which one follows in order to travel to unknown regions of the universe
This is a noun phrase. Now use this to modify the original noun:
'u' SepmeyDaq Sovbe'lu'bogh lenglu'meH He ghoSlu'bogh retlhDaq beside the way which one follows in order to travel to unknown regions of the universe.

That's not poetry. That's just complicated.

We’d be hard pressed to find another example where he does this. It fits the English translation pretty well, but it’s not grammatical in Klingon. Locatives don’t follow the verbs to which they apply.

He has not done that here.

So it doesn’t look like a great precedence-setting example for a verb in the middle of a noun-noun construction, unless we want to also accept that it’s fine for us to put locatives at the end of a sentence, now.

No one has suggested such a thing.

Your second example carries a lot more weight. Clearly, that is a noun-noun construction {romulusngan nejwI’} with the second noun being described by {Sambogh ‘ej HoHbogh}, which is also interesting, because it would be more typical of other canon to have said {romuluSngan Sambogh nejwI’ HoHbogh je.}, if I’m remembering the song lyrics correctly. Probably not.

It would be more typical of other canon to have said romuluSngan Sambogh nejwI' 'ej HoHbogh. There is just one time where a je was used for something like this, and that WAS poetry. This is not. Klingon canon has examples of both the X Vbogh 'ej Wbogh Y and X vbogh Y 'ej Wbogh forms, but only the one song with the Wbogh, Ybogh je X form.

-- 
SuStel
http://trimboli.name