After the events of Chamber of Secrets, it was clear to Dumbledore that Lucius Malfoy was behind opening the Chamber of Secrets (Dumbledore believed Harry & it seemed all the time that he kept an eye on Harry too). In subsequent years, he also discovered that Tom Riddle's diary was one of Voldemort's Horcruxes.
Why didn't Dumbledore suspect that Lucius Malfoy was a Death Eater? We didn't see him confront Lucius or at least, raise his voice against Lucius in the Ministry.
When Dumbledore confronts him about giving Ginny the diary, he knows and admits to Lucius that he can’t actually prove that Lucius was responsible for anything that had happened.
“Because you gave it to her,’ said Harry. ‘In Flourish and Blotts. You picked up her old Transfiguration book, and slipped the diary inside it, didn’t you?’
He saw Mr Malfoy’s white hands clench and unclench. ‘Prove it,’ he hissed.
‘Oh, no one will be able to do that,’ said Dumbledore, smiling at Harry. ‘Not now Riddle has vanished from the book. On the other hand, I would advise you, Lucius, not to go giving out any more of Lord Voldemort’s old school things. If any more of them find their way into innocent hands, I think Arthur Weasley, for one, will make sure they are traced back to you …”
- Harry Potter and the Chamber of Secrets, Chapter 18 (Dobby’s Reward)
The opening of the Chamber would have been the only thing Dumbledore could try to use against Lucius. Nothing from when the Dark Lord was in power the first time would have counted. After the Dark Lord disappeared, Lucius went to the Ministry and told them he was bewitched, acting under the Imperius Curse. Whatever he did during that time, he’d already gotten himself acquitted for it.
“I’ve heard of his family,’ said Ron darkly. ‘They were some of the first to come back to our side after You-Know-Who disappeared. Said they’d been bewitched. My dad doesn’t believe it. He says Malfoy’s father didn’t need an excuse to go over to the Dark Side.”
- Harry Potter and the Philosopher's Stone, Chapter 7 (The Sorting Hat)
Arthur Weasley suspected that Lucius did actually support the Dark Lord, and it’s very likely Dumbledore did too. From his notes in “The Tales of Beedle the Bard”, Dumbledore may have suspected Lucius was a Death Eater even before the Chamber was opened. He says, about Lucius’s campaign to get “The Fountain of Fair Fortune” removed from the Hogwarts Library, that the discussion they had over it marked the beginning of Lucius trying to get Dumbledore removed as headmaster and Dumbledore trying to make Lucius not the Dark Lord’s favorite Death Eater.
“This exchange marked the beginning of Mr. Malfoy’s long campaign to have me removed from my post as headmaster of Hogwarts, and of mine to have him removed from his position as Lord Voldemort’s Favorite Death Eater.”
- The Tales of Beedle the Bard
During Harry’s second year, Lucius was very clearly trying to have Dumbledore removed as headmaster - so their mutual campaigns against each other had likely begun before then.
He had no reason to suspect Lucius Malfoy of being a Death Eater, since he knew that he was one (especially after the end of Goblet of Fire). However, there's a big difference between knowing something and being able to prove it.
During the events of Order of the Phoenix, the Ministry was doing their best to deny Voldemort's return, discredit Harry and, due to his support of Harry, Dumbledore as well. That's a year at least in which his claims wouldn't even be considered by most at the Ministry, especially those in a position to do anything about it.
Tom Riddle's diary was a Horcrux, but after the end of Chamber of Secrets I don't know if there was any way to prove that. Assuming that there isn't, it's just a diary with no proven connection to Lucius Malfoy. Ginny and Harry's testimony wouldn't have been worth much, if anything; memories don't appear to be considered evidence (since they can be tampered with).
Lucius was a rich, powerful, influential and well respected wizard from a prominent family, without concrete evidence - of which there wasn't any - accusing him would have done no real good.
And, if Dumbledore had brought up the Horcrux, he would have done the one thing he absolutely didn't want to do: told Voldemort that he knew about them.
