Very interesting discussion in this thread. I think I understand both the goals which Forp tries to achieve and the reasons for it.
Yes. By your post I suppose that I finally managed to make myself understood. The idea actually also was reshaping due to the good discussion on the board here. Thanx to all, guys.
Of course, there is big flaw in the above - verification of block requires the same time as took to find the block, plus one needs to store all Kn chosen. But its an idea that came up. Feel free to improve on it 
.
.From what I see right now (have 2 leave train in some minutes and may need some more thoughts) this is identical to one of the non-parallelizable PoWs I found in the literature.
I am not so sure how big the problem of a long verification really is (could we overlap checking the last block with producing the next one ?). We are using PoWs in a bit different manner in Bitcoin than in, for example, spam and dos protection (where it is essential that the server can do a quick verification and the client does a complicated puzzle). In Bitcoin, we are more symmetric and would probably just slow down block production speed by a factor of 2.
Moreover, I just found some nice recent papers on non-par PoWs and I hope one of them contains a suggestion.