New
#31
I will find a better shop then
Unless you want to try then the shop is the best way to go.
I don't think I would tell second shop what first shop did... that will influence their thinking.
I would tell them they found it dirty and supposedly cleaned.
Ask them if they have the capabilities to swap components, in particular PSU and Video card. If they can't then ask them how they determine.
I would also ask for a cost estimate to replace thermal paste on CPU. It is an easy enough job so it should not be a crazy price assuming your case allows access to backside of MB. If not it could be total tear down.