Date::Calc is a good module. A search for Date on CPAN returns a lot of results. Another one that looks interesting is Class::Date (has relative date functions). I've never used that later but it's worth looking into.
I think one thing you have to figure out right off the bat is how to handle messages that should be sent on dates that don't occur every month.
"To be civilized is to deny one's nature."
Date::Calc looks like it will do what you want.
From the docs...
If the resulting date happens to fall on a day beyond the end of the resulting month, like the 31st of April or the 29th of February (in non-leap years), then the day is replaced by the last valid day of that month in that year (e.g., the 30th of April or 28th of February). BEWARE that this behaviour differs from that of previous versions of this module!