(T) Screaming brakes

I just had the car back from the 60000 km service. One of the things I asked them to look at was the brakes that are really annoying. Some 10 km into a ride they start making noise. At first it's just a soft squeak but after 20-50 km they start to scream. It's really bad. And it's not just one wheel. At one time at least three of the brakes where making a cacophony from hell.

The garage cleaned and lubed the brakes, including having copper paste on the back of the pads they say. But that obviously didn't help. The pads are far from worn out, still the garage suggests I should shift them since there might be a surface problem with them.

Anyone else had this problem and knows what helps? I don't feel like throwing away a lot of money for new brake pads if it won't solve the problem.

/Dan