Where are Mail.app rules stored? They got deleted and I want to restore them

Since Mail.app had trouble connecting to the various accounts, I tried to 'reset' it by removing all accounts and the stored passwords in Keychain Access.app. Then I re-added all the mail accounts.

However, for some reason all configured rules were deleted too, even though they are not directly tied to a specific mail account.

Where are these rules stored so that I can restore them from a time machine backup?

The rules are stored in a property list at:

~/Library/Mail/V2/MailData/SyncedRules.plist 

1. Restore this file from a backup.
2. Restart Mail.app.
3. Re-enable the rules.

These days check for a V3 folder (El Capitan). Restoring only the SyncedRules.plist may not work as another .plist file indexes the active state of the current rules set. What worked here was to go back to an earlier version of the ~Library/Mail/V3/MailData directory (note that it is in the V3 directory-- not the V2 directory). This takes a few minutes as Mail has to re-import your messages, but it did restore rules which were not restored by restoring the just the ~/Library/Mail/V3/MailData/SyncedRules.plist file only.

Here's an update to Charles great answer to restore lost Apple Mail Rules which you might lose when upgrading to Mac High Sierra OS10.13.4:

1. Close Apple Mail. Probably on your iPhone and iPad too.

2. On your Mac, go to iCloud and uncheck the Mail box so you don't replace the corrupted file from iCloud when reopening Mail.

3. Go to an uncorrupted backup copy of Mail. Drill down in your User folder: ~/Library/Mail/V5/MailData/
   be sure it's the V5 folder, then open it, find and copy the SyncedFilesInfo.plist file. Soon you will see it's older and bigger than the corrupted new file.

4. Now go to your current hard drive and drill down to the same User folder: ~/Library/Mail/V5/MailData/
   then open it, find and delete the newer smaller SyncedFilesInfo.plist file and replace it with your older, bigger backup file.

5. Now, reopen Mail. Your recovered rules should be there. Go to your Preferences>Rules and activate your rules by checking all the desired boxes. Add or delete a rule just to be sure the file updates itself. If that didn't work, repeat with an older backup file.

6. Now close Apple Mail, open iCloud Preferences in the OS, recheck the "Mail" box and close iCloud. Life should be all good again.