'After every restart ...', why so many restart's (reboots)? Restarts (reboots) are typically performed after an Apple System or Security Update, some third party software installations, when Apple's 'Safari' freezes MacOS X ('Tiger' only), plus a few other circumstances.
'... almost any application I open shows the message "You are opening the application "Whatever" for the first time. 'Are you sure you want to open this Application?'' - This is a 'Tiger' feature.
A constantly restarted, and not properly shutdown, Mac - should not be expected to operate (behave) as expected and save the files it needs to, during the shutdown process.
'I've repaired permissions', which have no effect on the problem stated, '... and run every disk repair utility I know, but the problem persists. Any ideas?'; but, you never explicitly state the names of the utility applications you used; nor, how you booted the Mac - in order to perform such disk repairs. Also, if you restarted (or even, just booted) the Mac and attemped to 'Repair Disk' via Apple's 'Disk Utility's 'First Aid' tab's panel - you cannot. 'Disk Utility' cannot repair the boot drive; but, you can (repair) other (non read only) volumes.
To repair your Mac's boot drive - you must boot from your (unknown version) MacOS X installation CD / DVD or another bootable volume, and run its 'Disk Utility' application - select your Mac's internal drive and then click the 'Repair Disk' button.