You say "On some occasions, again all under the same execution plan, poor performance occurs " but the execution plans you posted aren't even close to being the same.
The culprit here may be that the "good" plan was forced out of plan cache and when a new plan was made, it created a "bad" plan.
To answer your question, yes... statistics could absolutely be the problem here. And, it may not correlate with your larger data changes at all. It very well could be that the larger changes didn't quite "go over the edge" to cause an automatic update of statistics but a smaller data change may be the proverbial straw that breaks the camel's back and causes a statistics update, which would also force the code to recompile the next time it's executed and it would come up with a better plan because of the updated statistics.
I don't know if Azure allows you to lock in a known good plan like you can in SQL Server (I forget what that's called because I don't use it) but I probably wouldn't do that. I also wouldn't have a single stored procedure that joins so many tables. Instead, I'd break it down into smaller tasks making sure to identify the "core" (minimal possible set) that would drive all the other pieces and store it in a Temp Table.
I can tell you the process of "Divide'n'Conquer" can really work a treat. One company that I was contracted to work for asked me to setup a clone of a rather large system so they could do year end reporting. The funny thing is, they only needed to run one query. The reason why they wanted the clone was because the query would run for about 8 hours and bring the server to its knees rendering the server all but useless to anyone else (it drove temp db to the wall and it grew from a couple of gig to more than 500gig according to them)
I wasn't familiar with the data at all and so it took me a good hour or more to figure out what the "core" of the query was and then another couple of hours to get the rest of the stuff right but, the end result was a query that ran in less than 3 seconds and barely made a blip on the performance monitors.
The report was incredibly useful to them but they only ran it once per year because it crushed the server every time it was running. After I got it down under the 3 second mark (and super small amounts of Temp Table usage), they started using it every week and the info from the report save them a ton of time every week.
Yep... it'll take some work to determine what the "core" is for a query like this (and, there may actually be more than one "core") and it'll take a while to put things back together but, OMG, it's worth it.
Or, you could lock in the good execution plan and call it "done"... until that breaks and then do it again. And maybe again, and again again. 😀