Wife and I are looking to do a trip late-May/early-June to celebrate our anniversary. We'd like to go in the Pacific direction since we have been to Europe many times. We would also like to go to two different places (hence a 'triangular' itinerary).

Our first thought was OGG and TYO, but using united's multi-city search for OMA-OGG/OGG-TYO/TYO-OMA always yields really expensive fares for some of the legs.

The other alternative would be to book two round trips OMA-OGG-OMA and OGG-TYO-OGG, leaving a big enough time gap at OGG on the return, but I'm not sure if this would violate any united rules.

Also, we are not committed to OGG and TYO, if we found two other places where the triangle priced out nicely that would work too. We are also very flexible on dates.

Any thoughts/insights/help would be appreciated.

This is end-on-end ticketing and is generally fine.

Two thoughts:

1 - Go further on your first leg. In general, you'll get a better price on a circle trip (which is what you're describing) if the remote (Asian) leg is shorter than either of the overwater legs. OMA-OGG is shorter than OGG-TYO, which is causing the problem.

2 - Once you've revised your destinations, try pricing it two different ways. For example's sake, suppose that you selected HKG and TPE. Try pricing it as OMA-HKG/HKG-TPE/TPE-OMA using multiple destinations, and then try OMA-HKG/TPE-OMA using multiple destinations and then HKG-TPE with Kayak and compare the two. Sometimes you can get a better deal on an international one-way segment when it's not part of a larger trip.

What about an open jaw with a cheap one-way in the middle? OMA-OGG / TYO-OMA

And OGG-TYO separately, possibly not with United partners at all.

OGG-TYO is going to be problematic because it requires an HA segment. You'll probably do better with HNL, and can probably find a throughfare that allows a stopover at HNL on your way to/from TYO.

Another popular combination would be US-TYO-HKG-US, though the segment from TYO-HKG would be on another carrier (likely NH). You can also construct that as an open jaw, e.g., OMA-TYO, HKG-OMA, and then close the open jaw with a separate ticket on whatever carrier you like.

I agree with HNL. But if your routing is OMA-GUM-TYO, you will see # itineraries on UA 154/153. This is a truly unique experience via the Marshall Islands - known as The Island Hopper. Definitely anniversary worthy.

OMA/GUM with two stopovers seems to be one of the better ways to price this. HNL is easier on inventory since you don't need the HA flight, but I think OGG works with this construction too.

And it allows for the Island Hopper

For most Asian destinations (HKG, SIN, BKK, CGK, SGN etc) it might not be necessary to construct this as an open jaw — e.g. in the example above it's probably cheaper to price it/book as a USA-HKG rt with a stopover in TYO on one of the legs. UA on most TPAC fares allows you to add a stopover for $100, plus US-HKG/Southeast Asia fares are usually way cheaper than USA-TYO, and you don't need to close the open-jaw with another ticket. Have done USA-SIN-TYO-USA like this many times.

I'm not sure if UA still has the crazily cheap fares to DPS which they did last year but USA-DPS-TYO-USA might work as well? Or could also suggest BKK and TYO (and maybe go to HKT or CNX along the way as well).

Marooned on a small island in the Pacific. Quite an anniversary!
(I'm not being facetious.)

OGG is nice but I would consider doing the "tropical" stop in GUM. I found it kind of charming, familiar and yet mildly odd at the same time.

Try using Google flights to help planning. They can identify when you're better off splitting to multiple carriers.

In general, it looks like UA is not the carrier to pick for this trip.