Using Drupal 7.41 and Civi 4.6.9 (I suspect this issue affects earlier versions).
Our client is having an issue where not everyone received their scheduled reminders (they have 4 reminders set up with 1 for auto-renew only and 1 for expired). It turns out that the reason was because there was already an entry in the action_log for the action_schedule_id currently being processed. Most of the time it was the reminder with action_schedule_id = 1.
CRM/Core/BAO/ActionSchedule.php generates 2 queries in the buildRecipientContacts function. Here is an example of the first query:
INSERT INTO civicrm_action_log (reference_date, contact_id, entity_id, entity_table, action_schedule_id)
SELECT e.end_date, e.contact_id as contact_id, e.id as entity_id, 'civicrm_membership' as entity_table, 1 as action_schedule_id
FROM civicrm_membership e
INNER JOIN civicrm_contact c ON c.id = e.contact_id AND c.is_deleted = 0 AND c.is_deceased = 0
LEFT JOIN civicrm_action_log reminder ON reminder.contact_id = e.contact_id AND
reminder.entity_id = e.id AND
reminder.entity_table = 'civicrm_membership' AND
reminder.action_schedule_id = %1
WHERE e.contribution_recur_id IS NULL AND e.membership_type_id IN (1,4,2,3) AND ( e.is_override IS NULL OR e.is_override = 0 ) AND e.status_id IN (1,2,3,4) AND reminder.id IS NULL AND '20160115111124' >= DATE_SUB(e.end_date, INTERVAL 30 day) AND DATE_SUB(20160115111124, INTERVAL 1 DAY ) <= DATE_SUB(e.end_date, INTERVAL 30 day)
This part of the WHERE clause: "reminder.id IS NULL" is, I believe, causing the problem. If it already has a previous entry for the action_schedule_id being processed (say from last year) the reminder.id won't be NULL. It seems to me that it doesn't matter if it's NULL or not, if the rest of the criteria are met then a reminder needs to be sent.
Also, I think the second query (referenceQuery) has a similar issue in that it checks several civicrm_action_log table (reminder) fields are NOT NULL which would cause it not to add someone to the recipient list if there is no previous entry in the civicrm_action_log table.
I am not very knowledgable of the "overall picture" in this area of the code (well, not any other either really) so I would not be surprised if removing the reminder.<field> clauses would not fix things or would create other problems. I did test removing the check for the reminder.id in the first query and it appeared to work.