I've time to time got calls from telemarketers trying to sell Internet connections. This is one of the few services I might be interested in buying from a telemarketer and therefore I have some standard questions to ask from them. I ask for what I already have from my current provider. Telemarketers have improved recently. They are no more baffled by my requests but only state no, they don't have it.
I'm really happy with my current ISP, Nebula. They offer reasonably priced 24/3 ADSL connection where you are allowed to keep a server. One static IP address is included and more can be bought with single payment of 25 euros. This is quite fair as the only real expense for them is the time that someone has to use to assign the address to my connection. Also some other stuff is of course included (disc space, email addresses...), but I haven't been interested in them.
Nebula has a nice policy on what you can do with your connection: They don't care as long as you don't send unsolicited bulk email or otherwise break laws or do anything else really stupid.
But the best part has been their customer service. Whenever I have called them, the first person to answer has always understood my problem, listened carefully what I have already done to solve it, and then provided helpful answers withouttrying to read some manual aloud. When I sent an email to them on sunday after eleven at night asking for reverse dns entry in their records, I got reply fifteen minutes later that it had been done. That's something I'm ready to pay for.