Красный цвет пришёл из международного бренда My.com. Да, он похож на цвет одного из конкурентов, но если взять цветовой круг, то многие из основных цветов уже заняты (а синий, который изначально был у Mail.ru — вообще кроваво-красный океан).

Сочетание "красный знак в начале + чёрный текст дальше" и правда похоже. Но это скорее идёт от нашего давно существовавшего подхода "знак и текст разного цвета" (в продуктовом Mail.ru это издавна оранжевый + синий). Другие варианты применения этих цветов уже вымученные.