I (well, actually it was moset) discovered that PayPal doesn't show up in the market on frg83g, and probably gingerbread, too. I pulled the files needed to make an APK from an frg83d system with paypal installed and produced a working APK from it.
How I did it:
PayPal comes as a zip from the market. This alone contains only the resources (xml's, images, strings, etc) for the app. I found the code portion in dalvik-cache, but it was not deodexed. I had to deodex it using baksmali to produce a dex file. It required passing the maps.jar from frg83g deodexed framework passed as classpath. Then I inserted the dex file into the zip, called it an APK, signed with shared keys and bam! Working paypal APK. No idea why it was packaged in the way it was, but that doesn't matter now.