Если правомерны, то за какой период времени нам должны были это сообщить?

Что не находятся - вполне правомерно уведомили. Но вот относительно замены до 1 мая - вряд ли. Противоречит нормам закона - могут использоваться до истечения срока амортизации.

Федеральный закон от 22 мая 2003 г. N 54-ФЗ

"О применении контрольно-кассовой техники при осуществлении наличных денежных расчетов и (или) расчетов с использованием платежных карт"

"Статья 3. Порядок ведения Государственного реестра

1. При осуществлении наличных денежных расчетов и (или) расчетов с использованием платежных карт на территории Российской Федерации применяются модели контрольно-кассовой техники, включенные в Государственный реестр.

2. Порядок ведения Государственного реестра, требования к его структуре и составу сведений, а также федеральный орган исполнительной власти, уполномоченный осуществлять ведение Государственного реестра, определяются Правительством Российской Федерации.

3. Центральный банк Российской Федерации направляет в федеральный орган исполнительной власти, уполномоченный осуществлять ведение Государственного реестра, сведения о контрольно-кассовой технике, разрешенной к применению кредитными организациями, а также об используемых в ней программных продуктах.

4. Государственный реестр подлежит официальному опубликованию в установленном порядке. Изменения и дополнения, вносимые в Государственный реестр, подлежат официальному опубликованию в 10-дневный срок со дня принятия таких изменений и дополнений.

5. В случае исключения из Государственного реестра ранее применявшихся моделей контрольно-кассовой техники их дальнейшая эксплуатация осуществляется до истечения нормативного срока их амортизации".

Насчет уменьшения налогооблагаемой базы - уменьшится, в соответствии с НК РФ. Но, например, при ЕНВД - не уменьшится, там иной порядок расчетов, объектом налогоообложения является не прибыль (доход).