3.6V and 3.7V "labels" in this case, is merely a variation in naming and has very little to do with the behavior of the cells in question. It's just a lack of keeping up with the trends in the industry on ultrafires part. Years ago, lithium cobalt cells were charged to 4.10V, over the years, their have been improvements made that allowed these cells to be charged to 4.20V instead while still maintaining respectable cycle life. Since the charge termination went up by a tenth of a volt, so did the nominal rating of the cell. Today, cells labeled 3.6V are still going to be charged to 4.20V by any modern charger anyways. The performance differences from brand to brand are not going to be apparent by looking at what label voltage they have chosen to use.
It's a regulated flashlight so as long as your input voltage is above the minimum required to be in regulation, then it's going to be the same brightness. Which in your case, probably means anything above 4V input will work fine. So a pair of 3V cells is more than 4V, a pair of 3.7V cells is more than 4V, so there will be no difference in brightness...
Generally speaking, ultafire cells don't seem to be on par with the better names, their lower price really is one of those cases of "you get what you pay for" and unfortunately, that often means dud cells right from the package.
You mention availability of UF cells... not sure how available they are to you, but if you are still going to have to have them shipped to you, consider ordering direct from AW in his sales thread over on the CPFMP. He will ship world-wide for very reasonable rates.
Eric