La palabra carajo no tiene una procedencia segura, por lo que el propio Diccionario académico indica que es "de origen incierto".
De igual manera el origen de la expresión es incierto1, y aunque incluso en algunas webs "de confianza", como etimologías de chile lo apoyan, otras muchas lo desmienten.
La historieta en cuestión dice que a nadie le gustaba estar en la canastilla esa, que era un lugar peligroso, expuesto al frío, la lluvia y el sol y donde era más fácil marearse. Los marineros que no cumplían bien sus tareas terminaban siendo "mandados al carajo" como "castigo" para que escarmentasen.
Por tanto, explican que "mandar a alguien al carajo" era mandarles a ese lugar incómodo y de ahí la expresión.
Sin embargo esta otra web explica que esa historia sobre el origen es muy popular y extendida, pero falsa (y eso explica que no puedas encontrar en el diccionario en la entrada de carajo una referencia a la canastilla del mástil del barco).
Sin embargo, nunca existió en las embarcaciones sitio alguno al que le dijeran ‘carajo’. A los marineros díscolos simplemente se los encerraba en el calabozo, a pan y agua. Más agua que pan. Y la famosa canastilla, que sí existe, es en realidad el puesto del vigía y en castellano se llama ‘cofa’.
1- En el Diccionario académico, la voz carajo nunca ha tenido el significado de ‘puesto del vigía de los galeones’. La primera vez que se incluye esta voz en el Diccionario académico es en 1983, pero con otros significados.
El Departamento de «Español al día» de la Real Academia Española, ha encontrado el significado de carajo como cofa solo en el Diccionario náutico abreviado, de G. Poncio, L. Ballester, R. Nicotra y A. Will. Si esa única entrada es suficiente como para validar el origen de la expresión puede ser motivo de debate, debido a la escasez de evidencias (Habría que ver qué fuentes usan estos autores para atribuir a "carajo" el mismo significado que "cofa").
Aquí hay otro enlace de interés sobre el origen de la palabra “Carajo”.