SQL performance - Wierd behaviour

Hey Guys, I was hoping someone could throw some light on what in my mind is very puzzling.

Setup: Oracle 11.2.0.2 on Exadata V2

Table - 140Million+ rows

I have this query that takes between 70-80 seconds to complete. I know that is long and we are working with the vendor on this packaged application. This query runs daily as part of a batch job. For the last 10 days the query started taking 30+ minutes to complete. The data in the table grows about a million rows every business day. The OOTB stats gathering job runs in the maintenance window. 

Observations: We noted that the last analyzed date on the table was 1st Nov. Wondering why Oracle has not freshed up the stats we confirmed that the number of modifications in the dba_tab_modifications hadn't grown more than 10% of the total number of rows in the table. We also confirmed that the default staleness percent, of 10%, was at play. We also noted that the execution plan was exactly the same with the same plan hash value as the past execution history in AWR - dba_hist_sqlstat. The buffer gets, disk reads, cluster waits, iowaits etc were all seen to be