To answer your question directly...
If you have a mix of urls with and without pre-existing parameters (ie the ? char), you must find a way to separate them when building tracking templates, and manually use ? for the ones without parms and & for the ones with parms. Another workaround (although painful) would be to have a third party tracking server digest the tracking parms and redirect to your final landing page url (as an encoded lpurl).
Like you (probably), I spent a ton of time looking for an answer to this question and I am responding in the hopes that I will be contradicted with an actual direct link to the contrary.
On a related note, in the past, some feeds allowed for a way to add parameters to a url, whether it had pre-existing parms or not (as in google shopping, search for adwords_queryparm). So google is probably aware of this problem but some amount of common sense has been lost along the deployment cycle.