2nd Edition was much lower-magic than 3.5, so taking some hints from there might be good. For example:
2nd Edition mages were limited on how many spells of each level they could have in their spellbook, by their intelligence. This limit could be applied to all casters in a low-magic setting. Rather than hitting 'all' when you got to superhuman intelligence (raising ability scores was much harder; when you hit 19 int that limit would go away for a 2nd edition wizard and you can then scribe all spells) just have the limited number continue to grow slowly all the way up as int (or wis, for primary wis casters) increases. Suddenly no caster can know all spells, they must pick and choose. Add to that spells themselves being rarer and harder to come by, and caster power suddenly drops a whole lot as compared to the magic-mart worlds of 3.5 where the wizard is just going to buy scrolls of all the good spells next time he goes to town. Additionally, specializing didn't allow you to choose your opposition schools. Wizards would be somewhat weaker if specializing in Conjuration automatically banned Transmutation, and vice versa, for instance.
As for magical items...well, another 2nd Edition limitation might help there. First, magical item creation was harder, you had to get specialized components (determined by the DM - making a magical item was basically a blank check for the DM to send the party on adventures to gather the toenail of a cloud giant and the eyeball of a medusa and whatnot) and then you had to cast Permanency - which permanently removed one point of constitution from the caster. And since stats were also harder to raise... Suddenly magic items become very rare because nobody wants to permanently lose stats.
Granted, neither of these methods is going to be effective or balanced on its own, but they might be an interesting place to start. This allows things to be possible while making them more difficult. An equally large difficulty is balancing the monsters, and I think it may simply not be worth trying to adapt D&D to this sort of thing. As others have said, there are other games that are inherently lower-magic than 3.5 - including AD&D 2nd Edition itself.