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