Sorry if this sounds harsh but this thread should really say "My own lack of preparation left me in the dark". Only a bad workman blames his tools.
I'm not saying there is nothing wrong with the RCR123s you were using, and can say with certainty that the AWs will be better (and you need a good charger as well), but the problem here was not the cells letting you down, but you going into a situation where the light is essential with no proper backup.
The adage "One is none, two is one" should be ringing in your head. (and three or more is better)
I am interested in the scenario:
Had you tested the Ultrafire cells before trying them in a critical situation?
Had you charged them properly?
What charger do you have?
Did you measure the voltage after charging (and after an off-charger rest period)?
Are they protected or not?
If not protected, have you over discharged them and so reduced their capacity?
Others have already advised on the backup. Personally my backup will always have a primary cell in it and be capable of low output for extended runtime. The backup is just that, a last ditch light. If I am working and need light I would also have two work lights with spare rechargeable cells that have been used before and are known to be good.
Purely on the basis of capacity, I would be running 18650s, not RCR123. Your Quark with a primary CR123 would be good as a backup, but then you will need to invest in some other lights. Remember that if you are working, a headlamp may be the best choice as you have both hands free.
When you are able to prepare, there really is no excuse for being left in the dark.
By the way, I have cells which are no-name totally unbranded, Ultrafire and all the way up to AWs. The AWs are the best, and the ones I would choose if I had to rely on them, but apart from one or two dud cells from the cheaper lot, they have all worked reliably and within realistic expected parameters. The duds were weeded out by checking the voltage of the cells through their first few charge/discharge cycles.