Refus de réduction de préavis

Bonjour,

Voici mon problème:
Colocataire d'un appartement avec mon amie, celle ci vient d'obtenir dans un autre département un emploi d'aide à domicile. Nous avons donc effectué auprès de notre agence une demande de préavis réduit d'un mois, puis fourni une lettre d'embauche. Or, l'agence nous refuse le préavis réduit en qualifiant la lettre d'embauche de "complaisante" au motif que celle ci émane d'un particulier (l'employeur étant une personne âgée ayant recours aux chèques emploi services), et exige de notre part un bulletin de salaire "suffisant pour vivre". Au chômage tous les deux après nos études, nous ne pouvons payer deux appartements et avons déja loué ailleurs. Ma question est ici quels sont mes recours et a partir de quand peut on qualifier une lettre de "complaisante" et un salaire "suffisant pour vivre".

Merci d'avance

PS: pour l'instant nous avons décidé de faire parvenir une LRAR avec les textes de loi correspondant à la réduction de préavis et demandant un état des lieux rapide, puis nous déposerons les clefs directement à l'agence sans réponse positive de leur part (et en renonçant donc directement à la caution). Pensez vous que cela soit suffisant? Merci encore.