I carry a cheap dive knife I put a very good edge on in a bc pocket, but have never used it. I ordered the line cutter (trilobite) from Dive Gear Express and have used it several times to remove fishing line from reefs. They were on sale for less than $20 and have ceramic blades so no rust issues and the case just velcros around a strap.. For fishing line or small rope, they work amazing. I assume they would work as well on shoulder straps in an emergency as well. I'd like shears....but I no longer want to dive with everything but the kitchen sink.
I took a rescue class with a guy who had a knife that converted to shears. That was pretty cool but I think they were about $80.
As far as travel, we go to Mexico regularly and just got back from Honduras and had no issues with the scuba knife in my checked baggage.
Good Luck, Safe Travels.
Jay