No, monthly is used correctly in the first case. You are comparing apples to oranges here (or adjectives to adverbs).
Per The American Heritage Dictionary, 4th edition, annual is defined as:
adj. 1. Recurring, done, or pefomed every year; yearly: an annual medical examination
So annual is an adjective describing an interval. The word annually, on the other hand, is an adverb. Therefore, it cannot be used as you tried to in your sentence: This is an annually service. You could, as you suggest, write: This is an annually billed service. In that instance, the adverb annually is modifying billed, not service.
Month on the other hand is a noun, with the adjective form being monthly. Per The American Heritage Dictionary, 4th edition, monthly is defined as:
adj. 1. Occurring, appearing, or coming due every month: a monthly meeting; monthly rent payments.
It is grammatically correct to use monthly as you suggested: This is a monthly service. (As others have mentioned, monthly is also an adverb meaning once a month; every month. But in this example, it is an adjective.)