The fastest standard Celerons you can put in a BP6 in dual configuration are 533MHz original Celerons. Do not use the 533MHz Celeron II or faster if you want dual processors - it will not work.
Are you familiar with the concept of overclocking? This will give you the best bang/buck, and 366MHz Celerons are the best chips for this (it's what I and many others have in our BP6s). These can be found on eBay quite easily. Your 400MHz chips are also good candidates. Don't worry about the stepping, just get the same speed for best results. See this page for an intro to overclocking: http://www.pcguide.com/opt/oc/intro-c.html
If you want to run a single CPU in your BP6, you can buy a PowerLeap Neo adaptor and use a Celeron II or Pentium III. http://www.powerleap.com/Products/neo.htm
If you're good with a soldering iron, you may be able to modify your BP6 to take 2 PIIIs. http://bp6.gamesquad.net/mod_1.phtml But as you said, you don't really want to modify your BP6 and I wouldn't recommend it unless you're sure.
If you are running SETI on dual processors, make sure you use the command-line version of SETI. Install it into 2 separate folders, and run each one at the same time. That way, each processor will be crunching it's own instance of SETI, and you'll get 2 W/Us done in about the time it would take a single CPU to do one.
Hope this helps you, just shout if I wasn't clear enough.