From what i can gather it's even simpler than that. They'll need to contribute to securing the network in order to send a transaction.
Provided that the "proof" is not going to be a big hassle then that makes sense, however, having a very "cheap proof" will make it much easier to mount a Sybil attack.
The way I am approaching this problem is seemingly quite different to the other ways I've been reading in this topic (but as I haven't finished development yet I won't say more about it for now).