Akshully, I think it's possible to turn a blank piece of paper into a check, by writing the bank routing number and your account number on it, along with the name of the payee, the amount and your signature. If all that information is included, your bank should be able to honor it.
I've read that every year the IRS receives at least one check written on a shirt by some joker making a pun on "the shirt off my back". If the necessary information is included, they just go ahead and process it.
Checks are pretty univerally processed electronically nowadays. Just yesterday I paid my car insurance premium from my checking account over the phone, just by giving the insurance company the routing and account information. In less than a minute, the customer service rep informed me that my payment had been processed successfully.