I'm not sure that Ubuntu Server would work. The last machine I installed it on, the kernel required a CPU with (I just blanked on its name--that thing that lets 32-bit processors see more than 4GB of RAM); not to install, but to boot from the hard drive once it was installed. I'd be terribly surprised if an old Pentium supported that.
If it is a Pentium II it actually might. The Pentium II was based on the Pentium Pro, and I believe the Pentium Pro is when Intel introduced PAE.
And yeah, I noticed the PAE issue myself the other day, when I was messing around with Ubuntu Server in a VirtualBox VM. The installed OS wouldn't boot until I enabled PAE support for the VM...
If the world isn't making sense to you, you're either drinking too much or not drinking enough.