My Powerbook did that occasionally before the drive gave up entirely. I would "eject" the drive from Finder, the drive would disappear from Finder, but the disk didn't come out, and like you I wondered how to tell the computer to eject it when it didn't recognize that there was a disk in. The solution turned out to be to simply reboot, and when the computer came back up it recognized that there was a disk in the drive, and this time it would eject using the usual means. As far as the paper clip solution went, my PB didn't have the "little hole" on the drive so that wasn't a solution.
Don't know if this is similar to your situation, and if you've alread rebooted without luck then it probably isn't. But as I said, the drive died entirely a month or two later (wouldn't even TAKE a disk any more) so you might want to start making plans.
Scott