Moim zdaniem nazwisko Majek jest rodzime, a pochodzi od rzeczownika maj, od którego początek biorą liczne polskie nazwiska. Nie można wprawdzie wykluczyć, że jest obcego pochodzenia, ale uznaję to za mało prawdopodobne, więc chciałbym poznać uzasadnienie podanej opinii (może w dziejach rodziny są jakieś wskazówki, które by ją uzasadniały).
Jednak bez względu na pochodzenie nazwisko to należy odmieniać, zwłaszcza że odmiana nie powinna nikomu sprawiać kłopotu, skoro podobnie odmieniają się liczne wyrazy pospolite (np. kotek) i nazwy własne (np. Janek, a też najpopularniejsze polskie nazwisko Nowak).
Jeśli w korespondencji pojawiały się formy typu Waldemara Majka, Waldemarze Majku, a odbiorcy nie byli w stanie odczytać formy podstawowej nazwiska, świadczy to fatalnie o ich kompetencji językowej. W związku z tym decyzja Pani narzeczonego to nic innego jak kapitulacja przed nieuctwem. W tej sprawie zalecam upór, bo nie chodzi tu wcale o jedno nazwisko.
I ostatnia sprawa: owszem, każdy z nas ma szczególne prawo do własnego nazwiska, ale musi się liczyć z tym, że również inni muszą go używać. Proszę sobie wyobrazić, co by się działo, gdyby np. pewna liczba Nowaków zażądała nieodmienności swoich nazwisk. Język jest własnością wspólną tych, którzy go używają, w związku z tym nazwiska muszą być podporządkowane ogólnym zasadom użycia wyrazów w języku polskim, a ustanawianie indywidualnych zasad tego rodzaju jest absurdalne.