Why is gene finding in Eukaryotes such a difficult task?
The main problem is that while most of the things you describe are necessary to have a protein coding gene (introns, the non-coding regions within a coding region, aren't actually per se, even though they're common), they are not sufficient. Additionally there are also genes for non-coding RNAs (including tRNA and rRNA), which obviously don't have a 'coding region' (and also usually no introns). 

In order to classify something as a functional gene we usually require that is actually made into (at least) RNA, which requires regulatory sequences that lead to transcription of the gene, these are called promotors. In eukaryotes there are many different promotor sequences, so its very hard to predict them computationally, additionally there are evolutionary remnants in our genomes, which are called pseudo-genes, and while they still have the general structure of a gene, they are not actively used any more.