Right now, Services menu is available in Cocoa apps only.
As far as what items appear in there: This depends on your current selection (text or graphic or file or ...). If in a given app you have not yet selected any text, services that work on text (for instance, TextEdit's "Open File" or "Open Selection" or Mail's "Mail Selection", ...) will not not yet be enabled.
In your case sounds like Mail is not even being found as a valid service provider (it should normally appear under the same conditions TextEdit services appear).
Services are found by looking at various standard application locations --- Is Mail still in /Applications? Services are declared in the Info.plist file in the app package --- Has that changed by any chance in your Mail application package?
Ali