You are probably hitting a common problem with shared hosting: a fairly bad user (or a number of mildly bad users) or insecure script on your server that is sending (or allows other to send) out junk will result in all mail from that IP address getting suspected of being junk. Even if you have dedicated IP addresses for your websites and other services to respond to you will probably find your outgoing mail will appear to come from the same address as every other account on the server.
Likewise many problems in the host's range of addresses can get mail from anywhere in their range being considered suspect (though this affects all hosting arrangements, not just shared hosting).
It would be worth seeing if you can see the headers of the mails that are getting marked as spam and going into people's junk folders as some spam detectors will add notes to the mail headers to indicate which measures it used to make the judgement. This will save you trying to solve a problem that doesn't exist. Most anti-spam setups will just throw away mail that really really looks like junk by its measures. That is probably what is happening to those mails that are "vanishing into the void" - it is unlikely that they are getting lost at your end. For example, the headers added to an obvious junk mail to me when SpamAssassin picked it up were:
X-Spam-Status: Yes, score=9.959 tagged_above=-10 required=5.4
HTML_MESSAGE=0.001, RCVD_IN_PBL=0.905, RDNS_DYNAMIC=0.1,
URIBL_BLACK=1.955, URIBL_SBL=1.499, URIBL_WS_SURBL=1.5]
You can help the situation by setting up the relevant DNS entries for DomainKeys, Sender ID, Sender Policy Framework, ..., ..., ... for your domains, but if the host's IP addresses are in blacklists this can be of relatively limited utility.
If the hosts's IP addresses are on black lists you could ask the host to follow what-ever procedures are present to try rectify that. If they do not do this, switching hosts may be the best option.
You could also setup your own outgoing mail relay on a cheap VPS (even the "silly small" 1-or-2-$/month VPSs would run a simple mail relay for you) to separate your mail from that of other accounts on the server(s) you app runs on, but while you are probably the only person sending from the address you are assigned in that case you could still run into the problem of that host having all its range blacklisted because of other users.
To cut a long story short: there may not be an awful lot you can do in the end. Mail never was a truly reliable transport and it is getting increasingly less so due to the spam/anti-spam arms race, so you will never be able to guarantee all your mail gets through.