I've just upgraded to Windows 8 (from XP) and re-installed my copy of Office 2007. Now the common shortcuts (Ctrl–Z, Ctrl–C, Ctrl–V etc) don't work in Word, however other shortcuts (Ctrl–P) are fine.
These shortcuts do work in other applications (such as Chrome) and they even work in other office applications (PowerPoint).
When I go into the customize shortcuts option in Word I see that EditPaste command has Shift–Insert shortcut and I can add Ctrl–V but I can't find Undo and Redo.
BTW I'm using a Hebrew version of Office (I don't know if this is relevant).
Note: The accepted answer was edited after I accepted it. I didn't check that the modified answer is correct so be aware that the original answer (and the one that solved my problem) was to do with the currently selected input language when Word was launched, not the default keyboard language.
Best Answer
At last after a lot of searching on the Internet I found the solution:
You must select English as the default keyboard language (control panel -> regional settings -> keyboard).
If you select a non-English language as the default keyboard language and open Microsoft Word a lot of shortcuts will change to IBM Common User Access mode (e.g. Ctrl+C will change to Ctrl+Ins and Ctrl+V will change to Shift+Ins)
Note that if you set English as the default keyboard language everything will still work even while you're switching your keyboard language to type non-English text.
This problem appears in all Office versions from 2003 to 2013. It also appears in all versions of Windows since Windows 2000 and at least with Hebrew, Greek and Arabic languages but I guess with many (all?) others as well.
Note: For Windows 10 the above option is found under Control Panel -> Clock, Language, and Region -> Change input methods (under Language) -> Advanced Settings (on the left) -> Override for default input method.