I've been beating my head against my desk for the better part of a month trying to resolve this issue. Turns out my problem users had their addresses hidden from the Global Address List in Exchange. I have no idea who changed this, but I'm just glad it's fixed.