I've always had bad luck with Elitegroup/ECS boards, both Intel and AMD. I am a die-hard AMD fan myself, but I still build quite a bit of P4/Celerons for my customers (I build rigs and do repairs as a side-business). I had an ECS board for my AthlonXP when I got it (bought it from Fry's) and I thought it was just snazzy because it was free. Not too long after that I realized why it was free. Honestly, I'd use PC Chips over ECS any day, and that's sad
My favorite 3 brands of mobo's are Asus, MSI, and Shuttle for either CPU manufacturer. I also like Gigabyte, but they always seem to cram too much crap onto their boards and not testing them fully enough to see if it's all compatible. I'd still try them, if the other three are out of your range.
As for bargain boards, I've had good luck with ASRock (which I believe is owned by Asus, but I could be wrong) boards. ECS and PC Chips are usually pretty nasty and not worth money, even if they were free
As for your CPU, go with AMD. Intel's not moving into 64-bit for a long while on the Pentium side of things. AMD's already moved into it successfully, and I've seen many an A64 kick the crap out of a P4EE. Good luck on finding what you want.