The problems with schemes you are proposing is that you are assuming the 'Re:' and/or discussion depth should be part of the title. Assuming everything is stored in a database, what you need is store the title without any 'Re' prefixes in the database, along with a depth count. A root node would get a depth count of 0, a reply of 1, a reply to that gets 2, etc. The displayed title (at the post itself, or in the newest node list) can get a 'Re:' prepended. Or 'Re: Re: Re: Re:'. Or 'Re^17:'. It could even be user configurable.

One thing left open is whether a subject change should mean the depth count is reset or not.

Abigail