Wouldn't the most efficient way to mine such a coin be to be in an area with above average CO2 levels? Such as a closed room where you are burning oil/gas/wood? Have you heard of the cobra effect? See https://en.m.wikipedia.org/wiki/Perverse_incentive . Not saying what you suggest is impossible, but if it's possible to game the system I suspect it will be a net negative very quickly.

I think something like that would have to be manually audited by humans (i.e. you'd need to agree on a central authority who certifies volumes of carbon sequestered).

I was thinking the other day that maybe something that could be easier to objectively verify is something like a cryptocurrency where you generate a unit of currency when someone votes. Sort of like "I voted" stickers as a form of money. It's not a fully formed idea; I don't know how the logistics would work.

Bonus points if the currency as a whole is valued higher or lower based on individual voters rating their voting experience. Like, you ask them on a scale of 1 to 10 if they think they have a real voice in how their government is run. Thus countries would have an incentive to be democratic in a way that's truly responsive to the people and not just some kind of democracy theater.

Carbonminers would probably rather produce CO2 so they can "extract" it at much higher rate, instead of using the one in the atmosphere.

Edit: Ups this was already said.

Recently there was that blue-algae powered computer. Wonder if that concept can be used. But at ocean scale.

Make a government buying carbon. Like one cubic meter is $1000 or whatever cost would be interesting. Spend the money and bury those cubes in deep shafts. Let the market handle it.