Job Execution Information Not Written To System Tables

SS 2005 64Bit SP2

Hello Chaps

Intermittent problem with the SQL Agent job history not getting written to the history table. Background:
Today we noticed the account SQL Agent runs under cropping up in sp_who2. A quick check of the activity monitor said nothing was running. We ran a trace and, based on the SQL being executed, had a word with one of the developers who confirmed they had manually executed one of the jobs.

There was no record anywhere that the job had run. There has been an issue with this particular job, when executed by this user, not showing up in history before but, as mentioned, this had been intermittent and we thought that a restart of the service had sorted it.

Stuff run to try to track the job:
EXEC sp_help_jobactivity @job_name = 'MyJob'

EXEC sp_help_jobhistory @job_name = 'MyJob'

SELECT *
FROM dbo.sysjobhistory
WHERE job_id = 'MyJob GUID'

The first returned a row with no details in the columns indicating activity (e.g. last_executed_step_date and other columns were null).

sp_help_jobhistory had some historical records but nothing since mid last month.

sysjobhistory correlated with sp_help_jobhistory as you would expect.

Right clicking the job in SSMS and viewing history correlated with sp_help_jobhistory (i.e. some records but nothing since mid-June).

We edited the SQL in the job step and got the developer to rerun the job and, typically, everything appeared as it should in all the above result sets.
Obviously this is tricky to track down since it has been intermittent but does anyone recognise anything that I have described above? I have of course googled but there doesn't really seem to be anything about it.

We have considered there may be a problem in MSDB and may try running CHECKDB to see if anything comes up but somehow I doubt it will.

Ta!