I would suspect a leak like you said. When you do your soap test I would spray everything from the main tank connection, all the way to the last check valve in the hose (including the regulator, solenoid, NV, BBC etc). Also, pay particular attention to the right side safety valve in the pic below. It has been a source of leaks for some folks.
The next time you get your tank filled make sure you weigh it too. A 20 lbs alluminum is 25 lbs empty or 45 full, and a steel is about 32lbs empty vs 52 lbs full approximately.