The images speak for themselves. First image is with Anti Aliasing (2x default) and I read somewhere that turning it off fixes the problem, but as you can see on the second picture the problem still persists.
So in the very end the solution was the following:
- Turn off Anti Aliasing
- Create and new material using the default sprite and turn on the pixel snap option and apply it to the problem sprite
- In you sprite sheet (if you are getting multiple of them from the same image) make it so that the surrounding pixels are transparent
Without the 3. I still got some weird lines above the tiles. Combining all three fixed the problem for me.