It will depend on the specifics of the issue. Sometimes on Shared Hosting, someone also hosted on that server may have sent Spam emails which may have resulted in the Shared Server's IP being listed by one or more widely used Spam authorities. However, we are generally able to de-list the IP once we have traced the cause and the hosting account responsible for the Spam.
We generally scan for any IP blacklisting on an ongoing basis and work towards having those listings removed as quickly as possible, so it's possible that we are already addressing this and your services will resume as normal.
Please drop us a mail on firstname.lastname@example.org with all of the relevant details so that we can address this as quickly as possible.