Судя по всему, происхождение этого слова связано не с крымскими кочевниками, а с БАРДОЙ (БУРДОЙ).

Вот выписка из словаря Даля:

Барда - гуща, остатки от перегона хлебного вина из браги, броженного затора; идет на откорм скота. Отъелся, как свинья на барде. | Мутное, дурное питье, бурда. | Арх. грязные подонки и мутный отстой при перетопке сала, вышквар; кислая, загнившая ворвань; кислая огуречная слизь; | плохая почва (барда?), бесплодная, болотная или каменистая. Барденный, бардовый скот, барденик, скот, откормленный бардою, стоявший на барде. Барденный ларь, в который, после каждой выгонки, спускают барду из бражного чана (куба). Бардоватый, бардовитый, бардовистый настой, грязный, густой, мутный. Бардовщик, торгующий бардою. Бардинка ж. твер. порода небольших квасоватых яблок.

А вот еще:

БУРНУС = бур-нес - "бур (самогон из свеклы) несет" (отсюда БУРДА - "самогон дающая" - смесь, из которой делают вино, либо которая остается после его слива, отсюда БАРДАК - бочка с бурдой, а также последующее его переносное значение)

А вот КОГДА начали употреблять это слово в смысле "притон разврата" - таких сведений я пока что не нашла