We have always treated our 401k plans that have hardship withdrawals and loans in the following manner....

If the plan allows loans, you must take the loan first before utilizing a hardship.

We have seen different web sites that say that if the loan payment is going to cause an additional hardship, that the participant can then go directly to the hardship route.

Any legal trusth to this?

It is correct. If the loan would increase the hardship, it's not required.

IRS Reg 1.401(k)-1(d)(3)(iv)(D): "Employee need not take counterproductive actions. For purposes of this paragraph (d)(3)(iv), a need cannot reasonably be relieved by one of the actions described in paragraph (d)(3)(iv)© of this section if the effect would be to increase the amount of the need. For example, the need for funds to purchase a principal residence cannot reasonably be relieved by a plan loan if the loan would disqualify the employee from obtaining other necessary financing."