I would still lean towards the fan clutch not working properly. How did they test it? My 535i was doing exactly the same thing as yours, and although the fan was still spinning, it wasn't enough to cool things down when stopped or moving slow. There is a way to check with a rolled up newspaper, just gently put it up against the turning fan. As you increase the resistance, and bad fan clutch will stop, but a good one will keep turning and beat the newspaper. I could actually stop mine with my hand and spin it backwards while it was running. My new fan clutch MOVES a lot of air and it can be heard while driving until it releases.
If that's okay, there may be some air still trapped in your system, but that generally make you run hot all the time, so probably not.
Lastly, there is a small hose running down the left side of the engine compartment from the radiator to the expansion tank. When your car is cold, remove the cap and start the engine. As the engine starts to warm up, a small stream of anti-freeze will start to pee back into the expansion tank. If there is no flow there, your engine will eventually start to overheat. It's a small hole and clogs easily. Line from a weedeater works real good to unclog that little bugger.
These checks you can do yourself to save a few bucks.
Good luck!