I suspect many of the records can be recreated by contacting the supporting agencies. Go to your bank and ask for copies of the last 12 months of information; contact your vendors and ask for a recreation of purchase information, look at last minutes and see if there is a treasurers report somewhere you can see and then any information at the state and national level (like EIN information, incorporation information and tax 501 info or 990s) will probably be copied for you (usually at a fee).
If none of those pan out--well you don't have much recourse but to start over with a system you're comfortable with. Do it immediately anyway and don't let the whole get any bigger as you start a new school year. You can document your attempts, send a certified letter to the previous board and have the Principal acknowledge your efforts. Then without malice I would present the information (and your approach) at a PTO meeting to make sure everyone is aware what is and isn't available as you pull forward.
Finally--think about how you will reconcile this so it doesn't happen again. Start a filing system, audit system and have them maintained in a common location (perhaps the school has some space for a small filing cabinet for you or even a PTO room).
Go to the bank where your PTO account is held and let them know that a new board is in place and that the signature card needs to be updated. Most banks recognize that turnover occurs frequently with parent groups and won't hassle you. Once you've got your new signers (at least 2-3), you can request copies of old statements so that you have some information.
If you were a PTA I'd say to call your county chapter and get them involved; as a PTO the only thing I can suggest is asking your principal to speak to the outgoing pres and make it clear these are things that MUST be done. Then an audit should be done before proceeding any further to ensure your books are okay.
We had a similar problem this year (and we are a PTA)-our new board took effect as of July 1 and we are only this week able to get the new treasurer listed on the bank account so we can access the PTA's money. There was no problem with the funds, just an outgoing Pres that couldn't quite let go.
(Please note that while I may sound as if I'm pro PTA, the fact is I think PTOs are better for schools. However, there are a few circumstance where having that national organization behind you can be a help.)