What would be the optimal way to accept order payments from users who have Ether on an exchange? I can't figure out how to link the orderID with the transaction, without creating a new contract for each order, since they won't be able to add parameters/call functions. Also will the exchange run into gas issues sending ether to a contract account?
On this basis: "they won't be able to add parameters/call functions",
I imagine a separate contract for each expected transfer sets up the simplest external interface everyone can understand and implement without great difficulty.
A contract factory isn't especially challenging to set up. Plan to spend a great deal of time on admin, corner cases and testing of the immutable code.
A downside of such an approach is the site owner ends up paying for a small contract deployment for each expected payment (OpEx).
For the payment senders, yes, they will have to pay gas for function execution, but you could take care to limit things to the normal send() with only the gas stipend. A departure from "normal" would cause unwanted friction IMO.
Hope it helps.