There's a lot of confusion here, revolving around the use of "original".
The issue at hand, I believe, is that the customer wants to be sure they have the rights to use the designs without anyone claiming they're a copy of their work, and hence there is copyright (or possibly trademark) infringement.
The fact that you designed the logos from scratch does not necessarily make it original, if they're too close to other designs. If you see a painting, and then make a new painting that looks a lot like the first one, even though you started with a blank canvas, paint and brushes, it can still be a copy.
The same applies here: if your emoticons look to much like others, they may be infringing copyright. Your emoticons need to have something that makes them different enough from the originals, not just be created from scratch.
Note that in many cases, people make copies without even realising it. They have something lurking in the back of their mind which they have seen/heard somewhere, and they end up doing something similar to that.
Now, emoticons are a bit of a special case, as there are many, many emoticons that look a lot alike, even though they were created by different people, so it would probably be difficult for anyone to say "your emoticons are a copy of mine" if they also look like a dozen other similar emoticons. Also, to benefit from copyright protection, they need to be original work, and since many emoticons are just subtle changes on a list of emoticons defined by standards bodies, they may not be protectable/protected at all.
However, if your emoticons have a distinctive design that matches one that already exists, you could be in trouble.
So, options:
Make emoticons that are really different from any others. Make sure you do an exhaustive search for similar designs (e.g. using Google reverse image search). Note that it's difficult to be really exhaustive, but if you make a real effort and document it, that may help.
Make emoticons that look like emoticons that have "open" licences. Note that those may in turn be considered copies of other, "non open" ones, so you would be back to square one.
Just consider that emoticons are not protectable because they're too generic. You probably need to check with an IP lawyer before engaging in this route.
Be very careful of any wording you put in a contract or even in an e-mail. Consult a lawyer before making any statements as to the originality of your work. Consult a good lawyer before making any commitments/guarantees that your work is original or that you would indemnify the customer for any costs related to IP infringement.
NB: I'm not a lawyer. No guarantees, etc.