The problem is that the wall warts (new tiny ones anyway) don't use a stepdown transformer, they use a flyback transformer and a switching power supply. There are some step down transformers out there that are small, but not as small as you want. I went through this exact set of steps a while back and took apart a number of wall warts to see how they were actually constructed.
I suggest that you take a look for a small switching power supply to power the device. There are some of those in the marketplace, but they are much harder to find than DC-DC supplies. If you do some serious searching, you can turn up a few of them.
The other method is to come up with a supply that uses the AC input and reduces it to the 5v you need. The problem with this is that they are inherently unsafe to work on when the power is applied. Also, if a component fails, the entire thing goes up in blue smoke. It can be done though since X10 has been doing it for decades.