Ok, I finally solved the problem. It was something least expected by me so I will describe it in case someone comes up across something similar. I re-flashed my drive again to DVR-A16 but it didn't solve the problem, the drive was still in its slow mode. Inserting a disc again didn't help, nor rebooting or turning off and on the computer.
I managed to bring it back to full speed mode with Nero DriveSpeed by pressing "Fast" and then the black square button while I was copying files from the drive. I then existed DriveSpeed and from now on the drive was behaving as expected - slow for the first few seconds, then spinning up to full speed. So far so good. The culprit turned out to be Nero DiscSpeed 184.108.40.206, which I sometimes use to test discs, I use the only available quality test for Pioneers, which is Scan Disc/Read Test. The scan speed was set to 8X and this was causing the problems. The drive remembered the speed setting even after quitting DiscSpeed and was operating slow. I changed it to Maximum and now all problems are gone. I burned a new DVD+R and the verification went fast to the end. I suppose it would be quite hard for anyone to guess what was causing the problem.
My understanding is that DiscSpeed speed setting is behaving similarly to Quite Drive Utility, which can save speed in the drive. Because DVR-116D didn't support changing speed at all (DriveSpeed didn't work) then the problem didn't occur after using DiscSpeed read test.