I don't think the government can say "you were lied to about your car, stop using it" also VW can't force people to get the recall, why would you want to get a recall that worsens the performance of you car.
It's reasonable for governments to tell owners that they must get a software update or stop using their cars after some reasonable grace period while also forcing VW to compensate owners for their losses in doing this (eg. reduced performance). Essentially protect the environment as intended while getting VW to foot the bill.
The recall is mandatory for the consumers if they want to continue operating their car, at least here in Germany.
Of course they can say that. I think you are stating an opinion on this specific case and I'm sure you can imagine cases that may be a bit more extreme where you would reasonably say that the government shouldn't allow these vehicles on the road. But... I personally have the opinion that if these vehicles are polluting so far over the standards set as reported then they shouldn't be allowed to be driven or pay a "carbon tax" or be forced to get the upgrade, etc.
Couldn't they force the hardware/software modifications when people go in for yearly inspections?