I have come across some older servers running WSS 3.0 and MOSS 2007 in my time. More than once I have come across the inability to use 'Explorer View' on the server. After ensuring that there were correct security zone settings for the intranet site I started scouring the web when it still would not function correctly. After some snooping around I stumbled upon this:
Installing this fixed the problem on Windows Server 2003 and also Small Business Server 2003. Hopefully it will help those experiencing the same frustrating issue.