Check page 77 of the manual. There is a mention of this, I think:I never use single point spot but from reading that it seems like the auto focus points might be too small and are missing the assist beam? Is this the problem???
* With Single-Point Spot AF, focusing with the Speedlite's AF-Assist beam may be difficult
* If the camera cannot focus with the EOS-dedicated Speedlite's AF-Assist beam, set the AF area selection mode to Single-Point AF (Manual Selection) and select the center AF point to focus.
I'm not sure. I haven't tested extensively it yet.
I just got the 5DIII and reading your post reminded me of that section of the manual. My first upcoming clubgig is this weekend and I'll check out then.
I did a couple of quick shots at home with absolute darkness with the 5DIII and the 580EXII and it focuses pretty quick, I didn't notice any lag. I used the center and outer edges with AF expansion and SP-AF. Does the AF assist beam cover all the AF points of the 5DIII? Maybe that is the problem.