While that would work, you don't even need to do that much.

You don't need unique out addresses because even if you pay two (or 10,000) users from the same address, Bitcoin doesn't work on the concept of addresses and balances.  Each user will have unique inputs for their tx.   That is how Bitcoin works, it is how it has always worked, and it is how it always will work. 

You simply record the raw tx.  Thats it.  Nothing special.  Technically you don't even need to do that because the client/wallet already does it but for customer support it likely is easier to have that information available outside of the wallet.

Now for 99.999% of your transactions (if you are competent and not doing things like double spending your own coins, paying insufficient fees on masive spammy txs, and spending immature coins) the tx will go through fine.

For the 0.001% of transaction where user reports non-payment you:
a) check the blockchain to see if the tx exists by tx hash
b) check the blockchain to see if the tx exists by looking up the unique set of inputs and outputs which make the tx.

Why do a if b will find all txs?  Simple it is faster and tx don't accidentally mutate themselves so it gives you good information on which customers might be trying to rob you.  You don't have enough "evidence" to have them arrested, maybe not enough to even ban them, but you certainly have enough to flag their account so it warns other customer support reps to be extra vigilant.