I have used denture tablets to good effect on some rather dirty Model M keycaps.
Overnight is a bit long - did the water turn brown? Mine did after about 15 minutes.
Maybe try repeating the process, using warm water and leaving them in until the water turns clear (or brown, depending on how dirty they are).
You can also use, say, an old toothbrush to scrub the surface of each one a few times to remove stubborn dirt.