This sounds like an uncommon relationship.. or at least workflow.
In most situations, you'd present a design, if the client doesn't like the design, you rework it. Striving to make the client happy. But it's all billable. A contract should state as much.
Just because a client tells you not to bill them for something... that does not mean you don't bill them. It's not their choice what you charge for. However, a request like that would lead me to a discussion....
- The project was assigned. I spent X hours creating the project you requested. That time could have been spent on other clients and other projects. Instead it was reserved to complete the project which you requested. If I work on a project I expect payment.
- What don't you like?
- How can I edit this to better suit your needs?
- I will strive to create something you can use, but this is a billable project.
All that being posted.. if it's a long standing, great client and the project was minimal, only taking a couple hours or less... I may offer a considerable discount if they are unhappy. And in some instanced not invoice. However, I've never not invoiced because a client told me not to.