1. The two first links work on my end.
I don't know why your third link doesn't work. It's hard to say anything without the unSEFed equivalent of the SEFed URLs you gave.
Note that for next version, we'll add some options in order to change/remove the product/show or category/listing part of SEFed URLs.
2. That would mean that you would have to do one more query on the product page in order to know the list of categories of a product just to be able to know it, another query on listings in order to know if we need to add the parameter or not, and that wouldn't solve the problem when the product would be in several categories. Long story short, that would indeed be possible, but it's not a high priority for now.