What is the difference between Spray lubricants and non-spray lubricants?
You want a lubricant that isnt sticky. If it is sticky, dust will collect on your chain and form the gunk you are used to. This means: no oil. 

In my experience, spray lubricants can be more runny than bottled, because they can be formulated to evaporate the solvents more efficiently. It seems this is because the bottle seals arent that tight and the lubricant would dry out in the bottle. This leads to the chain feeling more dry when sprayed. I spray every few hundred miles.

Some spray lubricants are available in smaller, 150ml spray cans. 

The 450ml spray bottles last for years. I ride a recumbent with a long chain, and after two years the 450ml bottle is still half full. 

No experience with the paraffin thing. Unchaining a recumbent is no fun. 

I used to use bottled teflon based lubes, but by now I am fixed on sprayed, because it isnt as sticky, and seems to last longer. Just cheap lubes may not pay, depending on the price of the chain etc.