Написание Соловей Разбойник закреплено в тексте «Правил русской орфографии и пунктуации» 1956 г., но современной письменной практике оно не соответствует. Современные словари и справочники (например, орфографический академический ресурс «Академос» Института русского языка им. В. В. Виноградова РАН) фиксируют написание Соловей-разбойник. Это соответствует правилам: нарицательные существительные, сохраняющие свое значение (а Соловей-разбойник на самом деле разбойник), не входят в имя собственное и пишутся со строчной буквы. Ср.: Марфа-посадница, Маша-растеряша и др.