In a memo (as opposed to a more formal document) I might use "s/he deserves".

If I were to use the third option, I'd say, "Give every customer the service they deserve."

I come across this problem very often when translating from Greek to English since Greek is inflected and the personal pronoun doesn't have to be mentioned. What I usually do is use the plural to avoid the sometimes cumbersome 'he or she'.

Eg. "Give all customers the service they deserve."

>> "they deserve. "

[grinning from ear to ear] That post under my name was made by astral, by the way.