I ended up faxing a reservation to Hostal Gurea in Bilbao. Although they received the fax, they didn't responded to me by return fax or email. I had a friend who speaks Spanish call them the next day and they confirmed the reservation.
So it cost me 2 long distance calls and a lot more time than it should have. The Bilbao hostels are really missing out by not having internet access.
David