You're right about cilantro losing its taste when frozen, but I wouldn't say that it loses "all characteristic" taste. I think it does keep some faint taste if it is part of some kind of salsa, and the salsa is then frozen; or if it has been added to curry sauce and the sauce is then frozen.
Over time, I have learnt how to keep it in the fridge for longer than usual period and that is by washing the bunch, often just the roots if the leaves are fairly clean of sand or soil. The whole bunch is then put in a large enough container with water covering the root area. The whole shebang is then loosely covered with a plastic bag, secured around the container with a plastic band. This way I can keep a bunch for up to two weeks or more. This works well with watercress, asparagus and any other greens that need to be kept for a more or less long period in the fridge. The problem is that often there's not enough room on the fridge's shelves for everything.
BTW, you have fresh bay leaves? Where do you get them? The dry ones are pitiful really. A friend of mine bought a small plant in Montreal last summer. She promised to take me next year. I really want to get a plant of my own.