There are multiple possibilities depending on whether your accounts are IMAP or POP and whether or not the missing folders are On My Mac. As a trouble shooting step, try booting from your clone and see if the folders show up there. If they do, that would tend to point the finger at something on your computer.
If your account is IMAP, Mail reflects the status of your account on the host computer's IMAP server where the folders messages are physically stored and your next logical step would be to contact the email provider, because it is likely the failure is on their end, not yours. I have also seen situations where the email provider has made a change in their configuration which forced users to change the account setup.
If the accounts are POP3 and/or the folders were On My Mac then Artie's suggestion of restoring ~/Library/Mail from a Time Machine backup say 24 hours prior to your messages disappearing, or at least a point in time when you know mail was working, is excellent and the first thing I would try.
