Sometime a reboot fixes it, but not always.
That is the problem with intermittent behavior. It is difficult to say that "after" is caused by "before" because you don't know when the intermittent behavior will show up and when it will not. Any experiment in the presence of an intermittent behavior runs the risk of coming to a conclusion that is an "ex post facto fallacy".
I suppose your hypotheses of a damaged or loose USB connector is the most probable, given everything else you mentioned, although since you don't have a second Samsung/OEM charger, a problem with that specific charger can't be ruled completely out.
Note that the USB 3.0 Micro-B connector "extra" pins (the part of the connector which is not used by a USB 2.0 micro connector) doesn't have power/ground in it (there is a shield ground, but this isn't the same thing as the power supply ground)... so your tests with a USB 2.0 cable don't resolve anything about the connector, but do indicate that the problem is probably not your Samsung OEM USB 3.0 cable.
Those mini-usb connectors are pretty horrid mechanically for devices that need to be plugged in several times daily; I guess the phone industry assumes that consumers will toss their devices after two years, so the power connector only needs to survive about 1000 - 2000 plug-in/removal events.
The only conclusive way to eliminate the possibility that you simply have a failing USB connector would be to use a spare battery charger - and that means buying both a charger and a spare battery if you want your phone on almost 24/7.
Sorry I'm not more help.