It's based on the calendar year they initially registered and not the actual date. So even if their initial registration was on 12/15/05, they would still be required to renew on 12/31/06 because FinCEN would consider 2005 and 2006 as the two years. After that period then they would be on track for the full two year renewal. Here's an excerpt from the Q&A:
Money services businesses established after December 31, 2001 are required to register initially by the end of 180 days after the day they are established as money services businesses and to renew their registrations at the end (by December 31st ) of the twocalendar year period beginning with the calendar year in which they were initially required to be registered. Thereafter, registration renewal is required every 2 years by December 31st for as long as the business continues to meet the definition of a money services business.
MSB Registration FAQ