In lineages not directly discended from one another (though they do have a common (unicellular) ancestor). According to the article I linked to it even happened to prokaryotes, though “complex” multicellular organisms (whatever that means -- I guess cells not only bound together but also specialized?) ‘only’ evolved six times among eukaryotes.

It is possible that eukaryotes are particularly propense to becoming multicellular the way the OP claims bilaterians are propense to becoming intelligent, but I'd interpret each item of the poll to be conditional on all of the above, and I'd take “complex single cell life” to mean eukaryotes on Earth or similar.

I'm wary of calling cyanobacteria with their specialized nitrogen-fixer cells or the various colonial sporangia-forming bacteria 'multicellular'. They do some hellacious cell specializing within colonies, and there are other bacteria that form chains between reducing and oxidizing environments with bacteria in the middle passing electrons back and forth so as to allow the whole colony to metabolize things one bacterium couldn't, but it's arguably a little different than what we think of when we think of a mushroom or an animal.

Eukaryotes have however evolved unambiguous multicellularity on many occasions.