Android licensing strategy for publishing to Google Play and Amazon app store
I currently have apps on both the google play market and Amazon market and have not come across any of the issues you have mentioned above. I am using ecplise and created the apk file using a certificate and used the same apk file for both Android markets.
As they are seperate markets and as you mentioend Amazon has its own authentication meaning google play updates are not an issue and therefore need to be done on both Markets.
Google Play vs Amazon Appstore
Finally, things to look out for is if you have any links referencing the play market you need to change these to the Amazon market, as Amazon will fail it otherwise (upload to Amazon market can take several days), hope this helps.
When you submit the android apk file to the Amazon app store it signs itself and publishes the app. I uploaded by debug build (not even any signed apk) and amazon accepted it and the app is now in their app store. Amazon might have some sort of automated signing the application.
Make sure you've not implemented anything related to Google play store.
Good luck!