You didn't mention if you ever take any of those interns that e-mail you - but i presume you do? :)
My wet-lab lab also gets these direct "can i do an internship?" mails and we regularly take 4 or 5 a year. However we never get mail for bioinformaticians -- and man, we would love that. Everyone in the lab has some sort of bioinformatic problem going on. We did have a girl recently who knew a bit of R, and she did nothing but analyse data and make plots for 2-3 months. Was very rewarding for the lab... not so sure how enjoyable it was for her, but she never complained, and she got one hell of a good reference :)
tl;dr: Apply apply apply - if they don't respond to your first e-mail write a second to say "you're just following up because you're really motivated" after about a week. Make sure the mail is personalized else its going straight in the trash. etc. As they say, you make your own luck in this world.
Your chances of going abroad for an internship are slim to none. Who have you contacted in Finland? Doing thesis work in industry is rather common practice. For example VTT does lots of bioinfo stuff..
To people reading this thread in the future, don't take the guy above seriously.