From the FAQ. My Email Stopped Arriving - BlackBerryFAQ
Seems like you have done the steps.
2 additional solutions
1. Call the carrier and have them reprovision the device. Make sure you have the proper BB data plan.
2. Log into BIS and delete all of the email accounts, add them againa nd resend the service books.