[SalesForce] Batch Apex creating Duplicate records

I'm clutching at straws here a little, but has anyone ever come across a situation where a Batch Apex routine creates duplicate records, possibly as a result of the execute method running more than once for the same batch of records?

I'm having a sporadic issue where it appears that a batch routine is creating duplicate records, here are the particulars:

• Batch size of 1 (there are good reasons for that)
• Job runs daily every 15 mins between the hours 8am &
  6pm (00's of records processed)
• Job runs once at midnight for monthly load (000's of records processed)
• Issue only occurs in the midnight job
• Issue has only occurred twice in the last 18 months, with no apparent pattern
• Safeguards are in place to ensure only one job can run at any one given time (ironically, to prevent duplicate processing)

My code pulls a list of unprocessed records (in the start method), then processes them one at a time in the execute method. After each record is processed, it is marked as processed so not processed again.

Any ideas anyone?