Creo que la tesis citada por el cofrade Cuarteroni puede que sea la que más se acerca a la historia de este vocablo
Es decir, se trataría de una palabra con la que los marineros antiguos denominaron al palo MACHO (mayor), en su jerga, "carajo" (además la cofa asemejaría el glande
), y de ahí lo de "vete al carajo", "carajote" "acarajotado" etc. tras pasar un tiempo allí arriba.
En el sur (no sé en el norte) de España (Cádiz, Sevilla...) se utilizan estas expresiones con mucha frecuencia. Y no debe ser casualidad porque son ciudades con una muy antigua tradición marinera, y con muchas palabras y expresiones de origen náutico en el vocabulario de uso común ("tieso como una mojama", "perder la chaveta", etc.)