My initial thought would be that HP would have something to do with it.
As we are outgrowing the CG of the traveler thanks to crazy factors like my son wanting to eat food and reproduce at the cellular level, I am starting to look at other planes (Comanches).
But because I am a POA member, I thought "Can't hurt to see what Bo has to offer"
Much to my surprise, I see bonanzas that have a lower useful load than my traveler in spite of a significantly higher HP and at least 50 lbs of rudder missing. I'm guessing this is why F-16s are only 2 seaters now. HP seems to have little to do with what a plane is allowed to lift.
What determines the UL?
Useful Load is determined by two things: Max Gross Weight and Empty Weight. Period.
Empty weight is fairly easy to figure out. Less crap attached to the plane = lower empty weight. You can put your plane "on a diet" by removing old avionics, unused wiring, and quite a few other things, some of which can get pretty expensive. Some airplanes are also built like freaking tanks (like my Mooney, which is of "metal on metal" construction) and are quite heavy empty.
I think the question you're really asking here is more about max gross weight, though, and that can be affected by many things.
Structure is one, often related to how strong the wing attachments are and the forces placed on them. One can see this in the Twin Comanche: Without tip tanks, the MGW is 3600 pounds. With tip tanks, the MGW goes up to 3725 pounds, but that last 125 pounds must all consist of fuel in the tips. Since that fuel isn't causing any extra load on the wing attach points (at least in terms of upward bending moment), it's allowed.
Certification requirements are another factor. For example, I think it was from the 172N to the 172P, the gross weight went up 100 or 150 pounds. The structure wasn't changed. What was changed is the maximum flap deflection, which was reduced from 40 degrees to 30 degrees. There is a certification requirement that planes be able to sustain a positive rate of climb under given conditions in the landing configuration for purposes of being able to achieve a successful go-around even if a mechanical issue prevented the configuration from being cleaned up. With the 30-degree flap limit, the lower drag allowed the 172 to climb away from a go-around at a higher weight, so the max gross weight was increased. Higher HP can help with this one as well.
Spin characteristics are another certification requirement. Certified aircraft are required to be able to recover from spins in a variety of load and CG conditions. The DA40 has an available increased gross weight mod that consists of a collar on the elevator pushrod to reduce up elevator travel which changes how it enters a spin and allows it to recover from spins it enters at higher weights.
So, lots of different things can be the limiting factor in max gross weight. This certainly isn't a comprehensive list. There's also plenty of examples of people doing extra testing and/or otherwise changing the limits and getting STCs for increased max gross. Sometimes, it's strictly paperwork, meaning the STC holder likely just had to do some additional flight testing to prove the plane could meet certifications as manufactured at a higher weight.
@denverpilot has mentioned such a mod for the 182P, IIRC. Others, it's fairly simple mechanical mods like the aforementioned pushrod collar, the spar doublers that can be added to the Globe Swift, the VGs that allow many light twins to maintain control and climb at a lower airspeed on one engine, etc.
One other thing to consider is fuel. What you're looking for is payload, often incorrectly called "full fuel useful load". Every aircraft carries a balance between range and payload. If you look at how much fuel weight is needed to complete a trip, you'll find out what your needs really are. In the old 182 I used to fly, I'd get about 130 knots on 13 gph. That's 10 nautical miles per gallon of fuel, or about 0.6 pounds of fuel per mile. In the Mooney, I get 170 knots on 12 gph, or about 14.2nmpg or 0.42 pounds of fuel per mile. As a result, going on the same trip takes me less fuel and thus I have more ability to trade fuel weight for payload. To go to Gaston's would take me about 65 gallons of fuel with an hour reserve in the 182, while in the Mooney it only takes about 48 gallons with the same reserve. That's 17 gallons/102 pounds of fuel I can leave behind and use for payload instead.
It seems like a lot of the faster, higher-HP traveling planes have big tanks and give you more of an ability to either go really far without carrying much, or leave a bunch of fuel behind and carry a bunch of stuff a shorter distance.
I hope this was fun to read, considering it probably doesn't help your problem at all.