The P3 500 is a slot 1 processor. In order to get anything substantially higher you're looking at FC-PGA, so you'll need a slotket. I'm pretty sure the P3 700 was a 100 MHz FSB processor. There may have been a 750/800/850, I can't remember, but once you start getting up there, then they move to 133 MHz fsb. In order to ensure that it'll work you'll need a 100 MHz fsb proc, as with 133 you're running the AGP out of spec. You say you've overclocked this proc up a bit, so that shouldn't be a problem then.
Maybe with a BIOS flash you could get a tualatin in there, but most certainly a coppermine (up to 1.0 GHz IIRC).
Your board also takes SDRAM which is pretty much obsolete by todays standards. I see it selling for more than DDR ram nowadays too.
I'd suggest you just stick it out as is for as long as you can stand it, then get a new system when you can. You don't have to break the bank, but a 2500 barton, 512 DDR, all in one mobo, and the components from your current system will give you a great upgrade and for cheap.
If you really can't stand it for now, then see if you can find another 256 SDRAM for cheap some place and put that in. It'll give you a nice boost for a while and will tide you over.
Some day I'll be rich and famous for inventing a device that allows you to stab people in the face over the internet.