...and someone, posing himself as hosting provider, can collect them and scrape for their private keys
(or modify public keys)
You're right that there would ultimately be a strong incentive for memory/cpu service providers to reverse-engineer and monitor memory for keys, but I suspect there are ways around this.
It may be that trusting any one provider with too much is a serious hazard for agents.
(actually no agent would ever want to be running entirely on one system anyway as a simple shutdown might kill it)
Some sort of split-key system might work there, or it might require some of the new bitcoin scripting features.
Agents might need to share information on 'cause of death' and investigate(well.. at least monitor/record) each other's 'murders' and any pillaging by hosts - thus forming a sort of reputation system for service providers.