Are you sending it UPS? I went through a similar situation a few weeks ago with UPS, they swore my address didn't exist. It's on a 30 mile road with nothing but houses, I don't understand how they could have a hard time finding it.

Anyway, mabye try a different shipping carrier?