I'm only going to provide a high-level summary of an Ethereum-based protocol token so this doesn't get too tangled.
I think it will be helpful to separate concerns. Let's start with the "token".
You could power the App with Ether, but you've decided to define your own token. For that, you set up a "minter" contract whose main concerns are issuance, enabling transfer and tracking balances. Importantly, nothing to do with the App.
You bootstrap it with a structure along these lines:
mapping(address => uint) balances;
You create an initial supply in the constructor:
balances[aliceAdddress] = 1000000;
There. Alice has 1,000,000.
Alice can send some to Bob with the transfer() function. The transfer function checks the msg.sender's (Alice) balance and does a little math to subtract from Alice and add to Bob (recipient), assuming Alice still has enough. Google ERC20 for an emerging standard interface that makes this token compatible with exchanges.
The App
The App can extract a toll from any function. It might help to imagine midway coupons at a fair that were required to ride the roller coaster. The guy running the coaster doesn't handle cash ... you go back to the Exchange or cash booth to get more. Coaster guy just collects tokens.
So, your App is just taking signed transactions from users who want to do stuff, and delegating the transfer of a token from the rider (Bob) to the App. You decide what's fair and sensible. Your App can also award tokens. The rules are completely up to you. Think of designing the rules of the game. Your users can pack up their score and head to an exchange to "cash out."
Verification
This is an entirely App-level concern. It may be that verification is self-evident as something has unfolded inside the App (touchdown!) or it may be very abstract and external.
Abstract/External is harder. For something like storage, there might be verification bot that does a challenge/response interrogation of nodes to see if they can prove they can recover a shard. For a betting App, it might be an Oracle that feeds a trustworthy game result.
For IoT you might consider why the App should trust the meter. This varies on a case by case basis. For example, if the meter is known to be certified accurate/trustworthy then perhaps its data feed can be trusted. You could represent that with an access control list; let's only listen to vetted trustworthy sources.
In the case of a highway toll booth, perhaps your deployment scenario involves two IoT devides, both with wallets, both connected; one in the gate and one in the car. Perhaps naive and superficial but maybe the gate allows one car to pass for each payment received; generally the car standing there, but maybe the payment comes from mom who is far away and that's permissible.
So, for emphasis, verification is very much an app-level concern. You're right to identify it as a vital aspect of any design, or else the public will reject the app design, correctly recognising a garbage in, garbage out scenario. It has to be both believable and tamper-resistant.
Hope it helps.
