What type(s) of motherboards are you using? I read in here you need an AGP slot and not PCI-Express, but are you using a P4-based mobo or one that is strictly built for Celeron?
The main reason to look for a board with an AGP slot is if you plan on using an Ultimarc ArcadeVGA video card with an arcade monitor. The ArcadeVGA is currently only available in an AGP version. Another reason you might want AGP is to run Windows 98SE/ME. All the new PCI express motherboards only have chipset drivers for Windows 2000 and XP. 98SE/ME have no native PCI Express support and I've only seen one instance of someone who managed to get 98SE working on a PCIExpress motherboard and they did it with hacked beta drivers. No idea if it was stable or not.
To summarize: If you don't plan on using an ArcadeVGA and/or running Windows 98SE/ME, then you don't have to worry about AGP.
There is no such thing as a motherboard "strictly built for celerons".
A celeron processor is just a lower performance version of a P2/P3/P4 CPU. They use the same sockets and motherboards. Every board that you find that supports Pentium 4 CPUs, will also support P4 based Celeron CPUs as well.
Usually the Celeron's "lower performance" is achieved by by reducing the CPU's cache, lowering the front side bus, or removing features like hyperthreading.
The initial crop of P2 based celerons were awful because they had no L2 cache. Intel quickly changed that. Even though the cache is generally less on a celeron, often it makes little or no difference in real world applications. Usually, you need to run specific synthetic benchmark tests to show a difference.
If you're trying to squeeze out every last bit of framerate in order to run some of the unplayably slow games in MAME, then by all means, drop $1000 on a P4 Extreme Edition with extra cache and water cool and overclock it. But if you're just a normal person on a budget like most of us, The latest crop of Celerons are probably plenty fast enough.