Nope, it would only leave the 'Re:'s out of the title field, people could still change the titles, just not the number of 'Re:'s (stripping out any leading 'Re:'s would also be an idea). The depth wouldn't be off either if it was done properly, a thread's nodes aren't grouped by their titles.

As for display, I like the Re(3): format.

Update: Oops, might have misinterpreted your post. Are you referring to when a thread goes off-topic, someone changes the title to say "An off-topic node about cheese", and then the next reply is "Re: An off-topic node about cheese?" If this is the case, you're right, with my suggestion the reply might be "Re(3): An off-topic node about cheese" instead. It's a good point, but I don't think it's a major problem.