Number one what fuel cleaner did they use and how did they attempt to clean it?
If they used "Redex" and just ran it thru the engine for a few mins they need shooting.
Go to halfords and buy a product called "Slick 50" its about £15.99 but it works, Pop in a full bottle of that when your fuel light comes on, then fill your tank then take it for a run up the motorway, stretch your gears then take it for another emissions test, if it fail then id be check O2 sensors or poss your cat?