Redcare ~shouldn't~ interfere - at least not these days. I remember years ago (must be 10+), Redcare would interfere with DSL, faxes and PDQ machines but then BT revamped Redcare and the problem went away.
Just thinking in dial-up modem terms - do you have the option in your fax settings to cap the baud rate the fax connects at? It will make sending / receiving faxes slower but may make it more reliable. More of a workaroud than a solution mind.
Also thinking back to dial-up days - asking BT to increase (or possibly reduce) the gain on the line may help. Not sure if they still do this - but back in the day you could talk to faults and they would happily alter it - usually with a slightly sarcy comment along the line of "having problems with dial up speeds sir?".