Vegan mayonnaise never emulsifies?
Well this is ... disturbing. Switching to a different brand of soy milk let me succeed on the first try. I have no idea what the manufacturer of my usual brand does to it, but after more testing, even water+lecithine works better than that brand of soy milk.

I hope it's okay to answer my own question. For anyone who comes across this via Google in the future: I tried two different brands of organic soy milk with the same official ingredient list and no visible differences, and one consistently produces mayonnaise while the other consistently produces soup.

Thanks to all the nice people who took the time to try and help me!