It does sound like an ISP issue. But then again, it might also be related to this:
BearShare has been Sabotaged!
ISP's have a number of techniques. Shaping p2p bandwidth is one of them. Another is blocking such programs from connecting. Another is getting zero search results ... filtering the information.
You do know don't you that with a potential massive court case fine, BearShare sold out & is now owned by people who control the program & what it can do. See link above.