Try the BUDGET airlines
BOD seems to be a fairly popular destination for them, of course there will be NO miles.
www.flybudget.com has a more or less complete list for europe
also the travel24.de site (works in DE only as such!) now has an active map that shows all no-frills connections from german airports. Play with it and see whats there.
I used GERMANwings a week or so ago (actually it turned out to be an Airbus 320 in full EUROwings and Air Pristina livery)and was quite satisfeid with it. In jan they sell all remaining seats for 19 euro,all-in, thats even less as the airport tax.