В области написания прилагательных с не много словарного материала, то есть написаний, закрепившихся в языке и фиксирующихся в словарях. Так, есть прилагательное незамужний и соответствующее ему понятие (см., например, «Большой толковый словарь русского языка» под ред. С. А. Кузнецова). Слово немолочный пока словарями не фиксируется, хотя, по-видимому, в терминологическом употреблении формируются понятия немолочный жир, компонент (какого-то продукта). В этом же смысле в Вашем предложении возможно написание немолочный напиток. Но возможно и написание не молочный напиток, которое будет выражать идею отрицания принадлежности к молочным напиткам. Выбор должен определяться смыслом, который нужно передать и который проявляется в более широком контексте.
Лучше: были незамужними, жаждущими романтики.