Just checked 3 of our Windows 7 machines and this option still exists. It does look like many others have run into the same problem as you, one resolution being to edit the registry. I can't comment on this working or not from personal experience, but there are several users who claim this helped. If you're going to try this, backup your registry.
1. Click Start, All Programs, Accesories, Notepad.
2. Copy and paste this text:
Windows Registry Editor Version 5.00
[HKEY_CLASSES_ROOT\*\shellex\ContextMenuHandlers\Open With]
@="{09799AFB-AD67-11d1-ABCD-00C04FC30936}"
3. Click File, Save As, name the file "OpenWith.reg" (WITH THE QUOTATION MARKS) and click OK.
4. Now double-click OpenWith.reg, click Continue, Yes, OK, and see if the problem is solved.
It's possible that the 4 Windows machines you've looked at are off of the same image.
Source: http://answers.microsoft.com/en-us/windows/forum/windows_vista-desktop/right-click-open-with-command-missing-help-please/a9c3f139-075c-4285-b87d-25e899fb8b27