In Word 2007 this shortcut does work. However, I find Word's UI responsiveness for this shortcut a bit slow (only a few microseconds, but still..), so it doesn't really feel very natural using it. If you have never used this feature, I understand your response. I never felt a need for it either, until I discovered the feature in Eclipse and started using it. It is a very natural way of moving paragraphs, once you get used to it. And I miss it in the editors that don't have it.
It would be nice if the Evernote version for desktop systems (Windows, OSX, etc) provide keyboard shortcuts for moving paragraphs up and down. This feature is available in e.g. the Notepad++ text editor (ctrl-shift-up and ctrl-shift-down) and in Eclipse (alt-up and alt-down), and once you start using it, it is very convenient to reorder things.