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).
What would be useful is for MtGox (or a third party service provider) to have the ability to setup standing periodic market orders (i.e. buy $x worth of BTC every 24 hours at market). The company would also need a signed agreement with each employee on the amount of the election and clearly laying out the terms.
One thing which needs to be considered (and should clearly be articulated in the election agreement) is how will the exchange rate be calculated. The simplest method would be for the company to simply use the exchange rate at the time of payment. If the company owes an employee $1,000 in "bitcoin elected salary" the company on payday would buy $1,000 worth of Bitcoins at the current market price and transfer it to the employee. That is the easiest way but elected to but it diminishes the power of dollar cost averaging (what if on payday the exchange rate spikes up 10% before crashing back the next day). In my instance our company uses the volume weighted average price for the entire pay period. If the company does not have significant Bitcoin cashflow it would make sense for the company to to pre-deposit sufficient USD into an exchange account to handle employee Bitcoin purchases and buy in equal installments throughout the pay period.
Example: A company has 5 employees who combined have elected to have $6,000 of salary per pay period paid in BTC. The company would make a single wire transfer to an exchange prior to the pay period beginning. Say this company issues paychecks on the 1st and 15th of each month. Everyday during that pay period the company would buy $400 worth of Bitcoins. This way the company has the Bitcoins on pay day and they employee gains the advantage of dollar cost averaging.
As for accounting or tax implications. For the employer the accounting (from company book's standpoint) is no different than paying an payroll only in USD. Any costs beyond the payments to employees are operating expenses. Companies already have to withhold various taxes, and insurance premiums from an employees pay and the company then incurs the liability of making sure those payments are made. I am not a tax attorney but at least in the US there are no tax implications for paying an employee by alternate means. If the company realizes a capital gain (or loss) on their Bitcoin holdings they will need to account for that but this is true even in non payroll situations.
Example employee (based on this free tool:
http://www.paycheckcity.com/calculator/salary/ )
The example employees is opting to receive 20% of gross pay in BTC.
Semi-monthly Gross Pay$3,541.67
Federal Withholding: $309.13
Social Security: $219.58
Medicare: $51.35
California: $95.71
SDI: $35.42
Health Insurance Premium: $385.00
Bitcoin Withholding: $708.33 <--- this portion converted to BTC and paid to employee's BTC address according to terms of payroll deduction program
Employee Life Insurance: $5.65
401K (Employee Contribution): $177.08
Net Pay$1,554.42 <--- balance paid by check or direct deposit as normal. If employee did not elect partial BTC pay this amount would be $2262.75 instead
Calculation Based On
Gross Pay: $85,000.00
Pay Frequency: Semi-monthly
Federal Filing Status: Married
# of Federal Allowances: 2
Health Insurance Premium: $385 (pre tax deduction)
Employee Life Insurance: $5.65 Fixed (after tax deduction)
401K (Employee Contribution): 5% of Gross Pay (pre tax deduction)
Bitcoin Withholding: 20% of Gross Pay (after tax deduction)
As you can see Payroll is already complex and this doesn't include employer matching portion of 401K, employer's portion of FICA taxes, unemployment insurance, etc. Payroll involves a lot more than "paying the employee" It is taking a employee's gross pay and disbursing it to a variety of accounts. Often like in the case of taxes those funds are only paid quarterly but accurate payroll requires the company to account for the liability of those future payments. Adding yet another post tax deduction to a paycheck to allow employees to take pay in BTC is pretty simple in any payroll or accounting software.