UPDATE: As TimK pointed out, this isn't needed with jquery 1.5.2 any more. But if you want to add custom headers or allow the use of credentials (username, password, or cookies, etc), read on.
I think I found the answer! (4 hours and a lot of cursing later)
//This does not work!!
Access-Control-Allow-Headers: *
You need to manually specify all the headers you will accept (at least that was the case for me in FF 4.0 & Chrome 10.0.648.204).
jQuery's $.ajax method sends the "x-requested-with" header for all cross domain requests (i think its only cross domain).
So the missing header needed to respond to the OPTIONS request is:
//no longer needed as of jquery 1.5.2
Access-Control-Allow-Headers: x-requested-with
If you are passing any non "simple" headers, you will need to include them in your list (i send one more):
//only need part of this for my custom header
Access-Control-Allow-Headers: x-requested-with, x-requested-by
So to put it all together, here is my PHP:
// * wont work in FF w/ Allow-Credentials
//if you dont need Allow-Credentials, * seems to work
header('Access-Control-Allow-Origin: http://www.example.com');
//if you need cookies or login etc
header('Access-Control-Allow-Credentials: true');
if ($this->getRequestMethod() == 'OPTIONS')
{
header('Access-Control-Allow-Methods: GET, POST, PUT, DELETE, OPTIONS');
header('Access-Control-Max-Age: 604800');
//if you need special headers
header('Access-Control-Allow-Headers: x-requested-with');
exit(0);
}