This is such an important feature for K2, and the implementation is not impossible. First, I will say why this is important: Users should be able to navigate content listings, and find an item by different paths, without copying content between categories. So unless K2 can make NESTED TAGS (which would effectively be the same as multiple categories), this is still important. Think about Ebay or another retailer that puts links to items under "Bestsellers" and also "Video Games".
So how to implement? Here is the best way:
First, from the item creation, it can be assigned to multiple categories. 1 category is set as the primary category, and this category is stored in catid in the database (for compatibility). All other categories are stored in a new database table that maps items to categories by paths. The schema for this table:
ID (primary key) ItemID CatID PathID (optional)
The ID is just the primary key. The ItemID stores the article ID. The cat ID stores the CatID. The PathID is an optional parameter that reflects if this is path 1, path 2, path 3, .... to get to this item.
Any time an item is created, we make unique entries for each category assignment. This puts the database load on the item creation rather than search (if we had put all of the categories comma-separated in the original items table). When a category listing is requested, we just find all of the items in this Paths table that match, and list them. Other modules that use K2 should start using this table.
So for URLs, there is an SEO way and a non-SEO way, I want to highlight both, and suggest the SEO way.
SEO way: only 1 url per article. Unless some magical cookies or database are used, the page cannot reflect which category the user arrived by.
non-SEO way: multiple urls per article. This allows the URL to reflect the category that the viewer reached the item by. However, it also means that there are multiple URLs for the same item. This could be done simply by appending the "path" to the end of the URL to allow K2 breadcrumbs to properly display the path, or the whole url would be set correctly (the latter being preferable).
Let me know if this makes sense. The feature is quite important if K2 wants to be THE content solution.