If I add a reply-to header to the emails I'm sending, which is different from their from address, will it always work for my users no matter what client they are using.
I've been having situations where replies are going to the from address instead of the reply-to address.
This is difficult to answer. There is no hard-and-fast rule that clients must honor a Reply-To header. This is all RFC 2822 says on the subject (section 3.6.2):
The originator fields also provide the information required when replying to a message. When the "Reply-To:" field is present, it indicates the mailbox(es) to which the author of the message suggests that replies be sent. In the absence of the "Reply-To:" field, replies SHOULD by default be sent to the mailbox(es) specified in the "From:" field unless otherwise specified by the person composing the reply.
Note the use of the term "suggests". Also note that even where Reply-To is not specified, you still only SHOULD send to the From address.
SHOULD has a specific definition, which can be found in RFC 2119:
SHOULD
This word, or the adjective "RECOMMENDED", mean that there may exist valid reasons in particular circumstances to ignore a particular item, but the full implications must be understood and carefully weighed before choosing a different course.
The bottom line is that the standards leave this up to the email client, or possibly the user, and there are far too many mail handlers out there to really make any assumption about behavior globally. In my experience, client software usually honors Reply-To, but I have only been exposed to a small fraction of the wide array of client software that people might use.