what are typical (low-end) (wholesale) prices for modems (56k or less)
which can fit inside large handheld devices (the modem could be, say,
2 in by 3 in by 1 in) Some examples?

http://www.axiontech.com/prdt.php?src=PW&item=62823 less than $20? 28.8
You might be able to work quantity...

If you can actually get a PCI slot to work, you can get PCI cards for
$5 http://www.opsinas.com/catalog/product_info.php?products_id=1844
(note the small size, if you remove the bracket.