It is not a question about a reduced relative clause actually. The real topic of the question is the semantics of the sentences mentioned. The first sentence is not acceptable semantically without a defining relative clause who works at Costco. The second is acceptable in any case, for example, I gave a book to her last week.
Such difference is basic in relation to the types of the relative clauses, it is a defining one or not.
So, your question is about a determiner which could be put in the attributive position in the sentence, I gave (...) book written by Hemingway. If you put an indefinite article, your interlocutor, who understands English in accordance with the rules of the educated majority, can not understand what your real intention of conveying such information is semantically.
So, the right way of saying it is only that follows: I gave a book, which was written by Hemingway,...
The explanation according to the grammatical approach is here:
This notorious discussion contain many examples of unsupported personal opinions of informal speech users,