Edit in Microsoft Word/Excel or other office doc only works with Office 2000 and above, so you should be able to open it. (I know for sure that it doesn’t work for Office 97)

Check the following doc for differences between the various Office versions

www.microsoft.com/.../officeintegration.mspx

Make sure you have IE 5.5 and above and Office 2000 installed

My workstation is running IE Version: 6.0.2800.1106
Word version: Microsoft(R) Word 2000 (9.0.4402 SR-1)
Operating System: Microsoft Windows 2000 Professional

SharePointPortalServer
IE Version: 6.0.3790.0
Word Version: Microsoft Office Word 2003 ( 11.6113.5703), Part of Microsoft Office Professional Edition 2003
Server Operating System: Microsoft Windows Server 2003

So what do you think is going wrong ???

Note: I am able to open the same document  for Edit when I am logged in directly on the SharePointPortal Server with my ID (my ID is the same with which I failed to Edit the office document from my workstation). Also, each of these documents were initially created using office 2000.

To better understand, here's some more info: When I tried to open a Visio document, I received the same error  message on the workstation. i.e.
"'Edit Document' requires a Windows SharePoint Services-compatible application and Microsoft Internet Explorer 5.0 or greater."

I was searching the Net on the Error message and found the following link that says one needs Microsoft XP and above along with Office XP and above.

http://www.kbalertz.com/Feedback_833714.aspx

Let's see if what the writer suggest is the case.