My naive point of view would be that since it's not your decision to deploy or not, those stories should not be in your Kanban board but in your client's board (if they have one, or in their mailbox, or on their desk). You've finished your work (presumably, with tests asserting that the client's requirements are met) and now your work is done. If you're a DevOp shop and also responsible for deployment when the client decides to deploy, deployment activities should enter your Kanban board as separate cards (which is somewhat comparable to your current approach of putting the Ready To Deploy stories back to Product Backlog but makes it explicit that Deployment is a new story, not an unsuccessfully implemented story that needs to be restarted.)
Realistically, you seem to have a process problem and should talk to the PO and client about this. If they are blocking the deployment process, they are creating waste. You probably need to find out what causes the client to not want to deploy. Are they overworked and don't have time to do their part? Do they assume that stories that you marked as ready for deployment aren't really production-ready?
Shuffling stories around and creating more administrative overhead will not solve the underlying problem.
Edit: After some browsing, it seems that some would keep blocked tasks on the board, with some indication that they aren't waiting for your team to get around to them but blocked by external factors. This is mostly useful if elimination of the blocking factors is at least partly under your control and could be subject to process improvement (for example, if a task is blocked because requirements are unclear, you could work on getting better requirements for this task to unblock it, and find ways to get more complete requirements in future to avoid similar blockers). In your case, the blocking does not seem to be under your control, so I'm not sure whether this point of view is helpful.