My first thought would have been server load issues but it sounds like you've already checked that. Have you also checked the host? I don't know if it's possible (with your hardware) but it sounds almost like the host is going into some sort of power saving mode. If your host is a Windows server then it might pay to double check the power management setup and make sure that isn't potentially the issue.

Another thought was someone here recently was having a similar issue although sometimes it was unreachable at all. That ended up being an IP conflict. But as your server responds eventually then I doubt that'd be it.

Have you checked ping times (both when it's working well and when it's slow to respond). Doing a trace route might also be worth while (ideally in both states so you can compare) as perhaps there is something on you network (like a switch or something) that is on it's way out, or under-powered for what your network requires.

DNS resolution can also sometimes be the cause of issues like you describe. I would assume that you have a local DNS running? If so perhaps check that. Maybe it's being overwhelmed (or under powered for it's load)?

Also it could be worth keep an eye on the webserver logs. IIRC Redmine uses the Apache webserver so the both the general Apache logs as well as the access logs might be useful in troubleshooting this? Both should be found in /var/log/apache2/