Discussion of the hadith and it's authenticity
Among the 6 or 7 major sunni hadith collections only al-Muwatta' and sahih Muslim include a hadith with a similar wording as the one you have quoted.
While Imam Malik in most of the riwayat of al-Muwatta' has compiled this hadith as a hadith mawquf, which means it ends as a saying of the sahabi abu Hurairah without explicitly saying that these are the words of the Messenger of Allah (peace be upon him).
Imam Muslim quoted it with a complete (but different) narrator chain. But without quoting the part about "500 years" explictly.
Similar ahadit have been compiled in Musnad al Imam Ahmad (8665, 9680), by abu Ya'la (6690), by at-Tabaryni in his Awsat (1811, 5854) all on the authority of abu Hurairah (May Allah be pleased with him) as a hadith mawquf. It's also compiled on the authority of Abdullah ibn 'Amr (May Allah be pleased with him) (mawquf) ibn abi Shayba in his Mosanaf 36642 and on the authority of Ka'ab al-Ahbar (May Allah be pleased with him) in the same book 37744 which clearly say that this description is based on the Torah.
مَالِي أَرَى فِي التَّوْرَاةِ صِفَةَ قَوْمٍ لَمْ أَرَهُمْ بَعْدُ؟ فُحَشَةٍ مُتَفَحِّشِينَ فِي أَيْدِيهِمْ سِيَاطٌ مِثْلُ أَذْنَابِ الْبَقَرِ، مِنْ أَهْلِ النَّارِ. مَالِي أَرَى فِي التَّوْرَاةِ صِفَةَ نِسَاءٍ لَمْ أَرَهُنَّ بَعْدُ؟ نَاعِمَاتٌ كَاسِيَاتٌ عَارِيَاتٌ، مِنْ أَهْلِ النَّارِ
* * * (My own translation take it with care) * * *
Why do I see in the Torah a description of people I've not seen yet? obscene who commit profanities who are having flogs like the tails of the ox in their hands. Of the denizens of Hell. Why do I see in the Torah a description of women I've not seen yet? Who appear gentle and would be dressed but appear to be naked, among the denizens of Hell.
Note that a hadith on something unseen even if it was mawquf as in most of the narration logically can't come from the mind of a sahabi, so either he had heard it from our Messenger (peace be upon him) or by consulting books of the people of the book, as it was the case for Ka'ab al-Ahbar who was a Jew before converting, while Abdullah ibn 'Amr has collected some books of ahl-al-kitab.
Scholars like ad-Daraqutni have big doubt whether the narration chain in sahih Muslim is really correct and complete and ibn Kathir in his tafsir said that "Maybe abu Hurairah has narrated this on the authority of Ka'ab al-Ahbar as they used to "sit together" and discuss".
(This is a summary of what i could read in this discussion thread -in Arabic- about the hadith and it's compilation, maybe I toke a little bit the side of those who have doubts about the authenticity)
Am I correct in understanding that this is a quote from the Prophet Muhammad?
So there's -at least- a hint of a doubt that these are not the words of Muahmmad (peace be upon him).
The meaning of the hadith based on commentary's of the both major hadith sources
I'm referring to commentary's on al-Muwatta' like sharh a-zurqani and a-Tamhid of ibn 'Abdilbarr and Sahih Muslim like sharh an-Nawawi. Please also take a look at this fatwa which is a commentary of the hadith from Sahih Muslim and my only external English link so far.
First what is the meaning of the four major description of those women:
كَاسِيَاتٌ عَارِيَاتٌ مَائِلاَتٌ مُمِيلاَتٌ
Women who are naked even though they are wearing clothes, go astray and make others go astray
Women who are naked even though they are wearing clothes was explained as:
- Wearing from the gifts of Allah and naked from being thankful: So they have been given gifts from Allah and they were not thankful.
- Only parts of their bodies are/were clothed while other parts are naked to show their beauty.
- They wear thin (or skinny) clothes which are showing what they should hide either the body parts or the skin color.
Both last meanings imply that they are clothed only superficially, while in reality (it's like) they are naked.
go astray and make others go astray, is explained as:
astray from the truth or from the obedience of Allah and they make their husbands (or others) lose the right path also. Or they show and teach others to follow their way of misguidance.
strutting in the way they walk.
An other explanation is having a special hairstyle which is connected to prostitutes.
Does this imply that (believing) women who dress immodestly throughout their lives without repenting will not go to heaven? If so, where do they go?
Yes it would in sharh az-Zurqani two options have been quoted: they won't go to heaven with the others or without any former punishment this is based on Allah's will (based on verse like 4:48 or 4:116), whether he forgives or punishes.
How much of their body is required to be revealed before this applies?
Well you should know that scholars would say except hands and face (some would add feet) they should be covered in a manner that doesn't show their body, so tiny or skinny clothes are not allowed. Also read Verse (24:31) and the explanation from above about the description of those women.
Note some ahadith show that in the time of our Messenger (peace be upon him) even the polytheist women used to cover to some extent for example there's a story of Ali ibn Abi Talib (May Allah be pleased with him) who was following a fleeing woman who have hidden a letter (for the enemies) in her hair (I think in the pigtail), but once he "captured her" he didn't touch her and once she realized he knew she had this letter she asked him to turn away, so that he couldn't see her uncover her hair!
So one could have in mind that the culture and customs may play a role here when it comes to the definition what is appropriate or not. But I'm not the right person to discuss, as I'm not a scholar.
What does "smelt from the distance of 500 years" mean? Distance is not usually measured in years, nor is it smelt.
I think the hadith of al-Muwatta' gave a kind of hint on the meaning, but you may read my answer here on a similar question.
And Allah knows best!