Can you even buy 'used' software? When you pay for software, aren't you licensing the program, rather than just buying the physical disc?

Yes and yes. My understanding is that it's legal to transfer (ie, sell) the license of software you have purchased.

As far as backward compatibility with Photoshop files; this can be a problem. PSD files I save from CS2 won't open on some earlier versions, unless "maximize compatibility" is checked when saving.