Using ExtUtils::MakeMaker 6.56, I get the same results as you. When I still had 6.55_02, I got past linking to the original problem you had: 
C:\stager2\Zmodem>perl Makefile.PL
Set up gcc environment - 3.4.5 (mingw-vista special r3)
Checking if your kit is complete...
Looks good
Writing Makefile for Device::Modem::Protocol::Zmodem

C:\stager2\Zmodem>dmake
cp lib/Zmodem.pm blib\lib\Zmodem.pm
C:\progs\perl5101\bin\perl.exe C:\Progs\perl5101\lib\ExtUtils\xsubpp  
+-typemap C:\progs\perl5101\lib\ExtUtils\typemap  Zmodem.xs > Zmodem.x
+sc && C:\progs\perl5101\bin\perl.exe -MExtUtils::Command -e "mv" -- Z
+modem.xsc Zmodem.c
Please specify prototyping behavior for Zmodem.xs (see perlxs manual)
c:/progs/perl5101/site/bin/gcc.exe -c           -DNDEBUG -DWIN32 -D_CO
+NSOLE -DNO_STRICT -DHAVE_DES_FCRYPT -DUSE_SITECUSTOMIZE -DPRIVLIB_LAS
+T_IN_INC -DPERL_IMPLICIT_CONTEXT -DPERL_IMPLICIT_SYS -DUSE_PERLIO -DP
+ERL_MSVCRT_READFIX -DHASATTRIBUTE -fno-strict-aliasing -mms-bitfields
+ -O2         -DVERSION=\"0.01\"    -DXS_VERSION=\"0.01\"  "-IC:\progs
+\perl5101\lib\CORE"   Zmodem.c
Running Mkbootstrap for Device::Modem::Protocol::Zmodem ()
C:\progs\perl5101\bin\perl.exe -MExtUtils::Command -e "chmod" -- 644 Z
+modem.bs
C:\progs\perl5101\bin\perl.exe -MExtUtils::Mksymlists \
     -e "Mksymlists('NAME'=>\"Device::Modem::Protocol::Zmodem\", 'DLBA
+SE' => 'Zmodem', 'DL_FUNCS' => {  }, 'FUNCLIST' => [], 'IMPORTS' => {
+  }, 'DL_VARS' => []);"
Set up gcc environment - 3.4.5 (mingw-vista special r3)
dlltool --def Zmodem.def --output-exp dll.exp
c:\progs\perl5101\site\bin\g++.exe -o blib\arch\auto\Device\Modem\Prot
+ocol\Zmodem\Zmodem.dll -Wl,--base-file -Wl,dll.base -mdll -L"C:\progs
+\perl5101\lib\CORE" Zmodem.o -Wl,--image-base,0x3f000000  C:\progs\pe
+rl5101\lib\CORE\perl510.lib -lkernel32 -luser32 -lgdi32 -lwinspool -l
+comdlg32 -ladvapi32 -lshell32 -lole32 -loleaut32 -lnetapi32 -luuid -l
+ws2_32 -lmpr -lwinmm -lversion -lodbc32 -lodbccp32 -lmsvcrt dll.exp
dll.exp:fake:(.edata+0x34): undefined reference to `boot_Device__Modem
+__Protocol__Zmodem'
dll.exp:fake:(.edata+0x38): undefined reference to `boot_Device__Modem
+__Protocol__Zmodem'
collect2: ld returned 1 exit status
dmake.exe:  Error code 129, while making 'blib\arch\auto\Device\Modem\
+Protocol\Zmodem\Zmodem.dll'

[download]

Try 

cpan M/MS/MSCHWERN/ExtUtils-MakeMaker-6.55_02.tar.gz

[download]

Update: It seems I missed that this was already discovered

In reply to Re^4: XS build error by ikegami
in thread XS build error by pvizeli

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.