I personally think your system sounds ok, the added leak sealer is most likely the cause and also the engineer not wanting to get his hands dirty. As a few have said its most likely a boiler a fault as it really doesn't sound dirty.
As for power flush, in theses times I'm offering choices,
1 mains flush etc at est cost, but on flushing if we feel requires a flush we will offer it but not free of charge and all blame is shifted to customer
2 power flush from start at est cost
Note on early post of power flush at £380 that sounds very cheap, going rate is between £500-750 here depending on system and engineer
£500 - £700 for a power flush? Jesus, you either work for BG or you have an inflated opinion of how much work is actually involved in a power flush.
Fair enough if you can get away with charging that much but imo thats a very high price especially if it's just on a standard 3/4 bed house.
For me it's £500 +vat for a standard 3/4 bed house
My powerflush will also included correction of the problem ie raising vent, re piping CF & vent connections etc (materials not included)
Power flushing alone is not a solution
If your charging less your not putting enough time into it or under selling yourself.
You never mentioned the others were included, but if it was just a power flush then i still think over £500 is steep. Lets be generous and say you charge £100 for use of your machine & £50 for chemicals, your still getting £350 labour for a days work.
Good if you can get it but imo it's still a lot for something which is generally an easier day than installing. Each to their own though