Well, for posterity's sake, here's what I've found so far. I believe I have reached the end of this saga, but we'll see.

First after mirod pointed me to the perl-xml mailing list as the place of discussion for all things XML::LibXML, I found a post from the author that said this in response to the same exact problem I was having:

The stuff I wrote for checking that you can link to libraries doesn't seemt to work on Debian. Just comment out the check for -lxml2 and it'll work.

So I did that (though I do not know if this web host is running Debian). I ran make and discovered something was telling Makefile.PL to use 'pgcc' as my compiler. I've never heard of this compiler, nor, it appears, had my server. I dutiously added CC='gcc' to my command line, which now (for those keeping score) looked like:

perl Makefile.PL
PREFIX=/big/dom/xclickautomation/bin/perl
LIBS='-L/big/dom/xclickautomation/lib'
INC='-I/big/dom/xclickautomation/include/libxml2'
CC='gcc'
[download]

Rerunning make, I discovered that this did not override all instances of pgcc. I hand-edited Makefile to correct a line under the 'MakeMaker tools_other section'. Finally make ran as it should.

'make test' cropped up that some of the tests apparently wanted to use Devel::Peek. It would have been good to know this in the Prerequisites section of the Makefile.PL, but I suppose that tests aren't really part of the module itself. I probably would have skipped 'make test' except that this installation had already given me so much grief.