Must I remove the headers from the __CPP__ section and add them to the pre_head string?

Yep - that's what I'd be trying.
If the XS file that's currently being generated is of the form:

Perl headers
CV headers
Other code
[download]

You should be able (with the help of PRE_HEAD) to generate an XS file of the form:

CV headers
Perl headers
Other code
[download]

I don't know, however, if that will actually solve the problem.

Cheers,
Rob