What are the difficulties faced in doing this with a company who has never heard of Bitcoin, and probably has no interest in paying out in Bitcoins? Can they pay that pre-tax amount to an exchange? How does it work?
If the company has never heard of Bitcoin it will require a little work simply because there is no "bitADP" (ADP is major payroll provider in the USA) at this time. However if a company is interested it wouldn't require more than an exchange account that accepts wires from the US (like MtGox). The exchange account would be in the name of the company. The cost of the wire plus trading fees is still <1% which is a reasonable cost to provide this as a perk for employees (a cost of doing business, traditional payroll also has operating costs).
*snip*
Wow thanks for the informative post! From the looks of it, I really doubt the payroll department of a big company is flexible enough to add in an option to pay out in Bitcoins. There is a set up and manual conversion of money and stuff (unless MtGox does its automated market orders like you mentioned) that would have to be done by someone who has no idea what Bitcoins are.