I finally got my second lot of LEGO bricks sorted and started going through the third one. The first two lots were rather clean so there wasn't much else to do than remove all the trash and non+LEGO pieces from those. This third one is another story. The bricks are quite dirty and there is a lot of dust, sand and other small trash mixed with them.
After a quick web search I found there are many options to get your bricks clean. Some suggested you could even toss them into a washing machine or dishwasher and run them on gentle program to get them clean. Those bricks are sure near indestructible. The only two things that can destroy them are acetone (learned this the hard way when trying to remove some permanent marker drawings from some of my old bricks with nail polish) and teeth (the original brick separator™). Despite that I came to a conclusion that maybe that's not the best idea (mostly worrying about damage to the machines themselves).
In the end I decided to do it the old fashioned way: toss the bricks into a bucket, add some dish soap and water and give them a couple of swirls after they had soaked in the water for a while. Rinse and repeat.
Now my bathroom is full of drying LEGO bricks spread on all flat surfaces. And that's just half of them so far! I hope the cats wont scatter them all over the place during the night.