Hmm.
Okay, here's how I set up a test problem.
I have a layer with two stores, and they have a unique ID field called STORE_ID:
I have a layer with customers that has a non-unique field called STORE_ID that assigns each customer to a store.
Then I set up and run the tool:
It runs successfully and calculates a route between each customer and their assigned store. (The example is made somewhat confusing by the fact that the ID fields have the same name, but they don't have to.)
So, the ID field in origins need not be unique, but the ID field in destinations does.
If you're still having trouble...I'm not too sure how to help you. Might be best if you contact Esri Support, and they can look at your specific data and figure out what you're missing.