Обрабатывать строки как даты, как в вашем коде, не оптимально.
В приведенном ниже коде используются даты, а не строки, и используется та же базовая структура, что и в текущем коде. Хотя потребуется 12 запросов (по одному в месяц).
var currYear = DateTime.Now.Year;
for (int month = 1; month <= 12; month++)
{
var firstOfThisMonth = new DateTime(currYear, month, 1);
var firstOfNextMonth = firstOfThisMonth.AddMonths(1);
var totalSMS = (from x in db.Messages
where x.MessageDate >= firstOfThisMonth && x.MessageDate < firstOfNextMonth
select x).Count();
}