I've stuck Open-Xchange onto Debian + Gentoo boxes recently (literally - the last few days!), and it's fairly straightforward once you have all the Java dependencies sorted. Although I haven't seen any instructions for RHEL4, there are some resources for CentOS at the
Open-Xchange installation wiki which would probably be very, very similar.