Judging by how IOTA seems to be doing it it's not a big hassle, just a "small" PoW that a client has to attach to it's tx. Afaik the network will be depended on a constant stream of "honest" txs yes.
The problem with this is spam. IMO you cannot make the PoW easy enough for IoT devices while preventing desktop PCs from spamming the network; see this topic for more discussion on the subject:
https://bitcointalk.org/index.php?topic=1331522.0