The report execution has expired or cannot be found. (rsExecutionNotFound)

I have just encountered a similar error and symptoms after deploying Power BI Report Server October 2017 GA on a SQL Server 2016 Enterprise server. I had been running SSRS 2016 (and multiple versions before that) without issue. The error was occurring when clicking a URL link in a web page to run an SSRS/paginated report and generate it as a PDF so the user can save it to disk.  The same URL and report have been working for years, so the only known change was PBIRS.

Based on other posts I found, I added "&rs:ClearSession=True" to the URL and it worked immediately just by refreshing the web page containing the URL (no server-side resets or setting changes). I've had to use that parameter before with SSRS reports embedded in an iFrame. 

I know you don't want to or can't use that parameter, but the pointer to a session issue as opposed to Kerberos security, timeout settings, etc. was important to note.  Any further info you dig up will be great to post.