I'll admit my Norse mythology is rather rusty, but I do recall after an incident these two particular gods saw each other as mortal enemies and would eventually kill each other at Ragnarok. What was it that turned them against one another (I vaguely remember a story where Heimdal caught Loki stealing a piece of jewelry from Freya and kicked his ass over it but the details have eluded me)?
You are thinking about a story referenced in the Húsdrápa, which Snorri excerpted in his Edda. It plays out more or less as you described, except Heimdall does not catch Loki in the act, but is asked by Freya to retrieve Brisingamen. The only detail to add was that evidently Heimdall and Loki fought as seals. That is really all we know about it.
Further than this, as have already been noted, Loki and Heimdall will fight and kill eachother at Ragnarök. They also interact in the Lokasenna, a poem where Loki shows up at a party and insults the other gods. Heimdall does not seem to be under more fire than his fellow gods.
I don't think it was as much Loki doing anything to Heimdallr in particular as much as it was the fact Loki betrayed all the Aesir when he orchestrating Baldur's death. It is this reason that Loki was imprisoned to begin with.
It is prophesied that, come Ragnarok, Loki will escape from his bonds and join forces with the Giants against the Gods. After that, he runs into Heimdallr and the two mortally wound each other.
Basically, Loki killed Heimdallr's friend and then allied himself with Heimdallr's enemies.
Husdrapa, a poem by Ulf Uggason, deals with several mythological stories, including a battle between Loki and Heimdall. Arthur Brodeur's translation:
The famed rain-bow's defender,
Ready in wisdom, striveth
At Singasteinn with Loki,
The son of mothers eight and one,
Mighty in wrath, possesses
The Stone ere Loki cometh:
I make known songs of praise.
While it does say that Loki fought Heimdall it doesn't mention Freyja or indeed Brisingamen. Brodeur's translation refers to the object they fought over as a "stone" but other translations give it as "sea-kidney" (Faulkes) or "magic stone" (Wikipedia).
Snorri Sturluson's Prose Edda identifies it as Brisingamen. From his list of names for Heimdall:
He is also the visitor to Vagasker and Singastein; on that occasion he contended with Loki for the Brisingamen... Ulf Uggason composed a long passage in Husdrapa based on this story, and it is mentioned there that they fought in the form of seals. (Faulkes' translation: 76)
This in turn is often linked to the 13th century story Sorla thattr which describes how Odin got Loki to steal Freyja's necklace, so as to blackmail her into starting a war for him.
A simpler explanation is that Loki - 'Lopt', or 'fire' - is the deadly enemy of the watchman, of whom Heimdall is the archetype; that they were to be deadly enemies was practically a requirement, and so a reason must be supplied by the story-teller for their personifications to hate each other. In the end, the fire gets the fireman, and vice-versa.