The problem was that the address passed to mprotect wasn't aligned to the pagesize (4096). I've searched on google and found a rather old patch from Redhat that solves the error.
I've applied the attached patch on top of all the other ones from 4.3.0.dfsg.1-10 source and X is now running fine.
Just saw that I've deleted the patch tailored for debian, so attached is the original one from Redhat. The linux defines are already present in debian, so you only need the mprotect part.
Greetings, Piotr Kaczuba
--- xc/programs/Xserver/hw/xfree86/loader/elfloader.c.elfloader-linux-non-exec-stack 2003-01-24 12:26:35.000000000 -0500 +++ xc/programs/Xserver/hw/xfree86/loader/elfloader.c 2003-05-06 15:59:14.000000000 -0400 @@ -893,7 +957,7 @@ ErrorF( "ELFCreateGOT() Unable to reallocate memory!!!!\n" ); return FALSE; } -# if defined(linux) && defined(__ia64__) || defined(__OpenBSD__) +# if defined(linux) || defined(__OpenBSD__) { unsigned long page_size = getpagesize(); unsigned long round; @@ -2557,10 +2727,16 @@ elffile->lsection[j].size=SecSize(i); elffile->lsection[j].flags=flags; switch (SecType(i)) { -#ifdef __OpenBSD__ +#if defined(linux) || defined(__OpenBSD__) case SHT_PROGBITS: - mprotect(elffile->lsection[j].saddr, SecSize(i), - PROT_READ|PROT_WRITE|PROT_EXEC); + { + unsigned long page_size = getpagesize(); + unsigned long round; + + round = (unsigned long)elffile->lsection[j].saddr & (page_size -1); + mprotect( (char *)elffile->lsection[j].saddr - round, + SecSize(i) + round, PROT_READ|PROT_WRITE|PROT_EXEC); + } break; #endif case SHT_SYMTAB: @@ -2754,7 +2930,7 @@ ErrorF( "Unable to allocate ELF sections\n" ); return NULL; } -# if defined(linux) && defined(__ia64__) || defined(__OpenBSD__) +# if defined(linux) || defined(__OpenBSD__) { unsigned long page_size = getpagesize(); unsigned long round;