It's probably not abandoned property. The law of personal property in the state in which the gun was left is what counts, here, there's nothing special about it's being a firearm unless there's a titling/registration requirement as there is for boats, 'planes, and cars. But because the dude left it with you for safekeeping, you're a "bailee", and have a duty to protect it for him against others such as yourself.
First, don't take legal advice from people who aren't attorneys (i.e., licensed to practice law in the state you're in - a "lawyer" is merely someone who went to law school) including myself (I'm a "lawyer" as to your state). I'm pretty sure that the Lt. Commander is probably wrong, but I don't feel like checking up on it. The FAQ he cited tells what is permissible, not what is prohibited - you've got to look at the statute and the CFR's for that. The issue isn't "shipping", it's "transfer across state lines". I think (but again, I'm not sure) that there is no "transfer", since you're acting as the owner's agent in shipping the gun to the owner. A person can do through an agent anything he might do for himself if he chooses to do so. So your shipping the gun to the owner would be HIS act through you, not YOUR act. You cannot ship via USPS, though, unless you're an FFL.
As to mailing stuff for the purpose of setting up evidentiary situation: don't ever mail anything certified or registered unless there's a contractual provision, statute or rule of court that requires it. That's the best possible way to generate evidence that the person did not, in fact, receive what you sent. The best thing is to send the letter first-class priority mail with delivery confirmation and[/] a certificate of mailing. They'll look at you like you've got two heads when you say you want both, but they can't be used the same way in court, so you need both. A certificate of mailing is self-authenticating and can be introduced into evidence to prove mailing (you can rely on the legal presumption that something that's been properly mailed was properly delivered). The information you can print off the internet to show delivery confirmation can be used in rebuttal where a person says, "well, you may have mailed it, but I never really got it." That's done by saying something like, "Are you really sure about that, remember you're under oath, and let me refresh your recollection." then you can read off from the official website information and introduce it as a document for the purposes of rebuttal. When you send something certified/return receipt requested, the recipient can let it set in the post office for three weeks after which it'll be returned to the sender as undeliverable. No useful evidence at all in that, except for the other side.
It would cost more to do an action for declaratory judgment to prove the gun is yours by reason of abandonment than it's worth.
Why don't you just offer to buy the gun from the guy?
Then it'll be your gun, fair and square, and no problems.
People get themselves all balled up in trying to get something in an advantageous deal that they lose more than they gain in dealing with the inevitable complexity, rationalization, and other bull-droppings that they generate. It always turns out like an episode of "I Love Lucy". Just offer to buy the derned gun!