We are capturing the output, unfortunately the log file is empty and the time stamp of the file is not changing, which makes be beleive that BAT file is not getting executed at all.
In some case the BAT file is been called from DTS package. Package log shows the step executed successfully and time taken by job is 0 sec.
Will change BAT to CMD for couple of jobs and will see how they behave as compared to BAT files.
I have seen simialar problems with sqlmaint and it is due to something happening to the .dll in memory, thats why restart of agent is re-setting it.
copy the DLL over from another server thats ok
upgrade to SP4 could help you if this .dll is replaced by the upgrade