Which type of jet leaves black trail at cruising altitude? I was recently travelling to Morocco, and as I was sitting by the window, at some point mid-flight I noticed another jet travelling in opposite direction at our altitude. The reason I noticed it easily, was that it was leaving very dark, solid, nearly close to black colour trail. It definitely was at cruising altitude, as after that we were still flying for about 1.5 hours before landing. I just can guess that it was small-ish jet, as height of its body appeared nearly the same as diameter of the trail. I couldn't see much details any way, as it was about a mile from us.

Does the black trail indicates fuel inefficiency of an engine, and that could be on of the old military jets?
That could easily be a military jet, or it could be an older type passenger jet. The old jet engines had inefficient fuel injectors and simply used a lot of them, creating a higher fuel-to-air ratio which results in black smoke from carbonised fuel. There is only a short time to mix the fuel with the air under pressure in the combustion chamber, and modern day engines pre-mix the fuel with air before injecting.

Olden days jet engines also used water injection in times of high demanded thrust, creating more black smoke due to a cooler combustion chamber, but since the aircraft you saw was in cruise it would not be in a water injection flight phase. 

So any older type of jet engine could have caused the black smoke you saw. Could have been an old DC-9 or even a B-52 :)