Is Outlook working online and not offline on both machines? Is this on an exchange server, if so version please and version of Outlook. If you close Outlook down on one of the PC's that is showing as not read, then go back in and online is it still the same ?
Have you got OWA setup if so what does this show? Do they need to have Outlook open on 2 different machines at once, can they just not close one instance down and open when needed after all it only takes a few seconds or should do to open ?? If an exchange server, have you tried removing the exchange account and then adding on both machines, also try a full detect and repair on both and if no joy maybe type a few key words in google to see what that comes up with and work through any suggestions.