One of the Intel board would likely work fine but there are so many versions I do not have time to look on Intel.com for the ins and outs of each chipset. You have to be carefull some 865 chipset boards would only do a 533 MHz CPU buss so its all in the letters following the "865" that tells you want a board will do and that can be dug out of Intel.com if you want to bother.
I am about 90% sure that Asrock will be fine, just double check video card with ASROCK web site.
Several there should do the trick if it is a standard case. Offhand I like the :
AS Rock America ASRock P4i65PE-M Micro-ATX Socket 478 400 533 800FSB Prescott Mainboard.
AS Rock America
ASRock P4i65PE-M Micro-ATX Socket 478 400 533 800FSB Prescott Mainboard for Pentium 4 and Celeron CPU's with DDR AGP 8X Serial ATA 6 Channel Audio 10 100 LAN Micro-ATX Form Factor - Intel 865 PE Chipset
Boards with a "G" in the chipset number will have on-board graphics.
The Asrock (budget division of ASUS) should give good performane and be flexable enough to work fine. I would look up the memory and video card compatibility/specs on the ASROCK board before making a final decision.
Look through it carefully and remove any left over drivers. Make sure "show hidden devices" at top is checked and run through the system devices looking for non-Micorsoft stuff like USB drivers. Reboot and then install the drivers off the disk for the new motherboard. Reboot and do the video. Reboot and look in device manage again for any problems.