We'll start here:
Note: There are also fret buzzes on most strings but it only buzzes when playing an open string in the high E.
Generally, it sounds like your instrument has backbow. Your truss rod could be too tight, so that the strings rattle on the frets. The test is: capo the first fret, fret the last fret, and there should be some but not much space between the string and the 10th fret. The solution would be to loosen the truss rod, which is safer than tightening, but still, small changes and let it settle.
After it was returned, it was okay but I heard a rattling near the headstock (I suspect the truss rod was broken!)
If it was, then the instrument has serious, above-replacement-cost-for-most-instruments problems. If you loosen the truss rod and nothing happens, this is a sign of problems.
This is exactly the kind of thing you look for before accepting the repair.
But that aside, I didn't take it back and played with it intensively anyway and around 2 months later, the high E string buzzes when played in open, 1st, until 5th frets. It is very audible on clean or distorted but when distorted it sounds so horrible!
There's a lot there that would be easier to understand if I could hold it. Here I'm thinking either a high sixth fret or rather worn first-through-fifth frets and bad first-string but slot. There's a thing called a Fret Rocker, which is a piece of metal with four straight edges, which you can use to find if one fret is higher than the neighbors. I don't own one; it's more a luthier tool and less a player thing. If you can find something flat and stiff, that should work in a pinch.
But the solution — seating the fret, then leveling, crowning and polishing — is a thing few players I have met would take on themselves.
If your instrument has a bolt-on neck, you can get a replacement, but the new neck is not guaranteed to be without issues. That's at the far end of the solutions, though. Between truss rod, nut and fret job, most of your problems should be solvable.