What's the best way to handle a matching donation?
This is highly dependent on your development department's workflow - but I'd say what you described is the most popular approach.

If you do go this route, you may want to consider installing an extension I wrote called Auto Matching Gift.  It's mostly a labor-saver: When you enter the original gift, you select the Matching Gift organization from a list.  A pending contribution will be created on their record, and it will be soft-credited to the original donor.

Note that this was developed for an organization that pays for a service of all organizations that match gifts - so if you have to create the organization first, it's not much of a time-saver.  Hopefully one day I (or someone else) will improve it to allow adding organizations on the fly.