In my experience within different project teams the criteria for deciding what is accepted as a user story can vary quite a bit. My main problem is that some of the stories we create aren't actually desired functionality for the customer. For example:

As a... First time customer

I want to... Sign up to the mailing list

So that I can... Get updates on new products

I personally find stories like this are there just to appease the client and capture "expected" functionality. But they aren't always based on real insight.

Has any one else faced this dilemma or something similar?