If you really want to do covers and have a connection or two, try and contact the artist or who ever owns the music and get their permission. I used to be friends with a few "pros" that would gladly let anyone do covers of their music for free if they asked unless it was going onto an album. Then you could let the bar/resturaunt know their is no need to pay BMI anything.

Granted I have never played in a band so I never had that problem but if you could arrange it it then there should be no problem.

MSF