PC switch-on delay & requires everytime new BIOS setup

My PC runs XP-pro SP2, with Norton AV, anti-spyware, ZA, and DiamondCS ProcessGuard. Windows patch uptodate.

This problem has started happening over the past one month. Initially, the PC would boot-up only after some time (around half an hour) had elapsed from the main power on state.

Gradually, the delay factor has increased considerably. However, once the PC gets on, it behaves normal, and shutdown is also normal.

No problem with Software, it seems hardware problem. Once PC starts it has to reset BIOS everytime. NO battery problem, becasuse it ‘s just replaced.

What is the likely cause? Please suggest, Thanks.