More info on breadcrumbs (assuming that Previous/Next would be affected by this logic)
"Category Mappings help!!! Bug?" and "Products belonging to multiple categories, which category to display when view product", which leads to "Breadcrumb issue when product is in more than one category" (closed) workitem.
I would think that parameters shouldn't affect SEO. You see plenty of stores that add context information to their products URLs.
For example, if you look for a WD4000FYYZ hard disk on NewEgg (or any other item on a sale page), you get a URL with plenty of parameters (including a source parameter). But if you search in Google for NewEgg and WD4000FYYZ, you get a clean URL with only 1 parameter (to the product). Presumably the link rel="canonical" header takes care of this.
Support to keep in context products in multiple categories?
Not sure if it is a bug or if it qualifies for general discussion or feature suggestion.
When a product is in multiple categories, its breadcrumb defaults to the first one regardless of how you arrive to the product page, and the Previous/Next plugin iterates through this same first category (rather than through the subset you were viewing).
It's discussed a bit over on http://www.nopcommerce.com/boards/t/8174/incorrect-breadcrumb-for-products-in-multiple-categories.aspx. This discussion is a bit dated, unsure if there is newer/better info (or if Previous/Next has improvements on this).
This is counterintuitive, specially for Previous/Next plugin. If you arrive to a product through a category (like "On Sale", or through a manufacturer), you'd expect to be able to iterate only products in this category (not to land back in another list of products).
Implementation might not be trivial. Using a session variable (as suggested in the nopC board) can be fragile (ie, if you are visiting multiple pages on the same session in multiple windows/tabs). I'm guessing it would require adding parameters to the links when browsing the site using cats or manufacturers (so the product page can build the correct breadcrumb and Previous/Next can iterate the correct subset).