The final solution was to generate the link like so:
https://www.facebook.com/pages/<page id>/<page id>?id=<page_id>&sk=app_<FB_app_ id>&app_data=<deep link>
where deep_link is a relative URL with a query string that starts with a '?' and has the '&' characters replaced with '|' characters (poor man's encoding that I decode on the way in).
I saw several suggestions (mostly here on SO) to double or even triple encode the app_data URL - none of these worked, and usually they resulted in links that could not be posted by the sharer.php script.