In my mind this is the hardest problem to solve.
> - What is the proof-of-work scheme?
It doesn't necessarily need to be proof-of-work and I'd think it makes sense to piggyback off a different trusted network of some kind.
> - How can you be sure that every vote ends up in the ledger? Transactions usually get lost and sometimes takes few tries to reach to miner.
Do transactions actually get lost all that often? In my experience, transactions propagate the network pretty reliably and quickly. You can then look at the number of confirmed blocks to reliably check if its in the ledger.
> - Most important property is that not a single vote should be traced back to its caster. Blockchain is all public, how are you going to anonymize everything? IP addresses of transaction owners are already open.
IP addresses aren't stored, and the actual transaction could be layered on something like Tor to prevent tracing. You could also have physical voting centers. The important thing is that individual voters can verify their own vote.
One big concern I'd have that you didn't really touch on is around management of keys. In addition to identity verification, how do you handle theft of keys? If a key is stolen, how do you handle disputes to whats in the ledger? I would trust tech savvy people to keep their keys safe, but what about people who don't understand technology?