For future reference, it looks like there isn't a reliable way of doing it without a 3rd party app. Pdftk (http://www.accesspdf.com/pdftk/) ended up being my solution.
I first generated the FDF file as before, and then merged it into my PDF file using the following PHP code
header('Content-type: application/pdf');
header('Content-Disposition: attachment; filename="Download.pdf"');
passthru("pdftk file.pdf fill_form data.fdf output - ");
exit;
It was much easier than I thought it would be. This instantly eliminates the need to hack around with headers and file extensions to ensure all browsers handle an FDF properly, as it simply makes the browser download the PDF file.
If you want the PDF output file to no longer be editable, use
passthru("pdftk file.pdf fill_form data.fdf output - flatten");
Apologies if this is basic stuff, just thought I'd put it all in one place so that people don't go through the headache that I endured.
N.B. If your PATH variable is not set, you will need to use the full path to pdftk i.e.
passthru("/usr/local/bin/pdftk file.pdf fill_form data.fdf output - flatten");