Since when are banks allowed to pay interest on regular checking accounts?

They are not - it has to be a NOW account.

Just checking; a local paper published an ad where a bank was offering a checking account that paid interest. No mentioning in the ad of restrictions. Thanks.

It is most likely that the "checking" account is really a NOW account.

There is no specific requirement that ads for NOW accounts explain the qualifications for such accounts, although I agree that the use of "personal accounts only" or "personal and non-profit accounts only" would go a long way toward making the ad more transparent.

There is also no requirement that the word "checking" be further explained in the ad. Since "checking" can refer to any transaction account, it can encompass conventional DDAs, NOWs and ATS accounts.