I'll let you read up on the URL structure and decide on what you think, because I've read conflicting opinions on the effect of structure and usually use short, concise, extensionless URLs myself, but
there are times when it doesn't make sense or can't really practically be done because of the size of a site and I end up using longer ones than I would normally like to.
Personally, I think the URL structure could probably be overcome from a search engine perspective, but from a visitor perspective IMO they're a bit ugly, so if it was my site I would think about making the change.
At the same time, I would not want to lose the traffic, rankings, bookmarks, links and other 'goodies' that come along with having them the way they are, so I guess my 'short personal answer' is: If I could redirect them and get the structure so that's the way they will stay (really think it through, because Cool URLs Don't Change
[w3.org]) then I'd probably do it and get it out of the way, but if I couldn't find a way to redirect them I'd probably leave them alone. (Until I could find a way to do it at least... :)
IMO and In My Experience, there's usually a way to do the redirecting, but sometimes a higher degree of 'creativity' is necessary than others. In some cases you can simply redirect from one to another using a regular expression and in other cases you might have to build a database to do the redirecting at all efficiently. The difference is usually in whether you need to access the new full URL to determine what it is (or build it) from a fragment or not.
Is a fairly easy association to make...
RewriteRule ^p/([0-9]+)/ http://www.example.com/product/$1 [R=301,L]
This is more difficult, unless there is a consistency in the number of hyphens, which there probably would not be...
The reason is if there are a different number of hyphens you cannot consistently tell where the artist-name stops and the name-of-product starts, so I would probably switch from mod_rewrite to PHP, because it's possible with PHP (and fairly easy, IMO without looking at the site, if you keep the same product numbers in the database when you make the change) where with anything except very advanced mod_rewrite you'd have to do it individually. (It's actually not impossible to do AFAIK with mod_rewrite, but it's more of a 'technical challenge' than it is with PHP IMO.)
Anyway, I'd probably change them right after I found a way to do the redirects, because IMO when thinking about what they look like to visitors 'short and clean' is in, but I'd also want to make sure once they're done that's the way they stay...
As far as 'ugly with the numbers' goes have at look at the URLs here... They used to be all numbers
, then they were finally switched to text for the directory names... Maybe so I didn't have to try and remember what forum number this was when I wanted to type a link or go straight here? IDK, but I like them better as text for the directory name and the numbers aren't hurting (and didn't hurt) the rankings any.