Force index on a delete
The solution I have found for my problem with the help of @jkavalik was to:


Move the DELETE statement into a DB Event that runs every minute.

CREATE      
  DEFINER = 'admin'@'%' 
EVENT backup.DeleteProcessedRecords     
  ON SCHEDULE EVERY '1' MINUTE  
  STARTS '2015-10-20 11:10:18'  
  ON COMPLETION PRESERVE    
  DO  
BEGIN   
  DELETE FROM backup.records WHERE readyToBeDeleted = 1 ORDER BY deviceId;        
END

add the ORDER BY deviceId to the DELETE Statement.
change the Index IDX_records_readyToBeDeleted from (readyToBeDeleted) to (readyToBeDeleted,deviceId).


Now I am waiting to see if I still get as many deadlock as I had before. I will keep you posted @jkavalik. And once more thank you for your expertise.