How to fix ‘Not A Valid Win32 Application’ Error?

I can’t open any application from Microsoft. I am receiving an error like this:
Application.exe is not a valid Windows 32 application.
Booting from Safe Mode did not help. Why am I receiving this error and what do I need to do to fix this? I am using Windows XP and all the software and applications are up to date. Please help.
