http://support.asus.com/cpusupport/cpusupport.aspx?SLanguage=en-us
You can see here if your CPU it is compatible with you MB.
These are All the CPU that P5S800-VM will suport an Bios versions
Celeron D 325J (2.53 GHz, 533 FSB, LGA775) ALL ALL
Celeron D 326(2.53 GHz, 533 FSB, LGA775)E0,EM64T ALL 1007
Celeron D 326(2.53 GHz, 533 FSB, revG1, LGA775) ALL 1016.005
Celeron D 330J (2.66 GHz, 533 FSB, LGA775) ALL ALL
Celeron D 331(2.66 GHz, 533 FSB, LGA775)E0,EM64T ALL 1007
Celeron D 331(2.66 GHz, 533 FSB, revG1, LGA775) ALL 1016.005
Celeron D 335J (2.80 GHz, 533 FSB, LGA775) ALL ALL
Celeron D 336 (2.80 GHz, 533 FSB, LGA775)E0,EM64T ALL 1007
Celeron D 336 (2.80 GHz, 533 FSB, revG1, LGA775) ALL 1016.005
Celeron D 340J (2.93 GHz, 533 FSB, LGA775) ALL ALL
Celeron D 341 (2.93 GHz, 533 FSB, LGA775)E0,EM64T ALL 1007
Celeron D 341 (2.93 GHz, 533 FSB, revG1, LGA775) ALL 1016.005
Celeron D 345J (3.06 GHz, 533 FSB, LGA775) ALL 1005
Celeron D 346 (3.06 GHz, 533 FSB, LGA775)E0,EM64T ALL 1007
Celeron D 346 (3.06 GHz, 533 FSB, revG1, LGA775) ALL 1016.005
Celeron D 351 (3.2 GHz, 533 FSB, LGA775)E0,EM64T ALL 1007
Celeron D 351 (3.2 GHz, 533 FSB, revG1, LGA775) ALL 1007
Celeron D 355 (3.33 GHz, 533 FSB, L2:256KB, revG1, LGA775) ALL 1016.005
P4-3.40 GHz Extreme Ed. (800 FSB, HT, revM0, LGA775) ALL ALL
P4-506 (2.66 GHz) (533 FSB, EM64T) ALL 1007
P4-506 (2.66 GHz) (533 FSB, EM64T, revG1) ALL 1016.006
P4-511 (2.8 GHz) (533 FSB, EM64T) ALL 1007
P4-511 (2.8 GHz) (533 FSB, EM64T, revG) ALL 1020.001
P4-516 (2.93 GHz) (533 FSB, EM64T) ALL 1007
P4-516 (2.93 GHz) (533 FSB, EM64T, revG1) ALL 1016.006
P4-519K (3.06 GHz) (533 FSB, EM64T, revG1) ALL 1016.006
P4-520/520J (2.8E GHz) (800 FSB) (HT) ALL ALL
P4-521 (2.8GHz, 800 FSB,HT, L2 1MB) ALL 1013
P4-524 (3.06GHz, 533 FSB,HT, L2 1M, revG1) ALL 1021
P4-530/530J (3E GHz) (800 FSB) (HT) ALL ALL
P4-531 (3GHz, 800 FSB, L2 1MB) ALL 1013
P4-540/540J (3.2E GHz) (800 FSB) (HT) ALL ALL
P4-541 (3.2GHz, 800 FSB, L2 1MB) ALL 1013
P4-550/550J (3.4E GHz) (800 FSB) (HT) ALL ALL
P4-551 (3.4GHz, 800 FSB, L2 1MB) ALL 1013
P4-551 (3.4GHz, 800 FSB, L2 1MB, revG1) ALL 1016.006
P4-560/560J (3.6 GHz) (800 FSB) (HT) ALL ALL
P4-561 (3.6GHz, 800 FSB, L2 1MB) ALL 1013
P4-570J (3.8 GHz) (800 FSB) (HT) ALL 1005
P4-571 (3.8GHz, 800 FSB, L2 1MB) ALL 1013
P4-630 (3.0E GHz, 800 FSB, L2:2MB, EM64T, HT) ALL 1007
P4-640 (3.2E GHz, 800 FSB, L2:2MB, EM64T, HT) ALL 1007
P4-650 (3.4E GHz, 800 FSB, L2:2MB, EM64T, HT) ALL 1007
P4-660 (3.6E GHz, 800 FSB, L2:2MB, EM64T, HT) ALL 1007
P4-662 (3.6 GHz, 800 FSB, L2:2MB, EM64T, HT, revR0) ALL 1016.006
P4-670 (3.8 GHz, 800 FSB, L2:2MB) ALL 1007
P4-672 (3.8 GHz, 800 FSB, L2:2MB, revR0) ALL 1016.006