[SalesForce] Is it possible to use images in Visualforce generated PDFs which are not static resources

It isn't necessary to go through a VF page in order to create a PDF. Instead, you can write your own custom PDF controller that's called from a button on an existing page (one that has queryable links to all the data objects you need) and then have the completed PDF output in a new window. If you're looking to automatically save it as a file, there are some autosave methods you might be able to use in conjunction with what I'm describing, but I've never attempted or had the need to do something along those lines with a PDF Controller.

Since you say you're able to create XFDF files using APEX, I'd expect that writing the VisualForce controller shouldn't be that difficult for you. The way I've done these in the past is to create an HTML template with custom CSS. Then it became a case of populating fields and using repeats wherever tabular data existed. There are also some "tricks" here and there in the CSS that can help with pagination if that's something you need to accomplish. Also, some people lay out the complete document in the controller, then send it to the page while others simply send it to the page. There's a tutorial in the SF documentation on writing a PDF controller using the former method. Unfortunately, I don't recall at the moment which workbook it's in.

From the "What about embedded images? Are images downscaled?" section of The Flying Saucer User's Guide (the technology usually assumed to generate PDF in Salesforce):

For intrinsic width/height calculations we assume a resolution of 96 DPI, but setting an explicit width/height makes it possible to use an arbitrary DPI.

In repositories such as https://github.com/flyingsaucerproject/flyingsaucer there isn't obvious evidence that the max-height and max-width are supported for images. So try width or height instead in your CSS.