OK, anyone who's tried a few different iPhone or iPod accessories has probably seen this annoying message. The smart people on http://www.head-fi.org have figured out the answer.
The answer is 68k.
To understand this, you need to know a little about the iPhone/iPod dock connector. The dock connecter is a 30 (tiny) pin connector on the bottom of the phone. Through that connector, you can communicate through USB, communicate through a serial protocol, get audio out, get video out (with some limitations), and (on older models) communicate via FireWire. One of the pins is called the "accessory pin" and that pin controls what type of device the phone thinks it's connected to. By using different value resistors between that pin and the "ground" pin, the phone will be told what type of device (audio out device, charger only, laser gun, x-ray machine, etc.) it's connected to.
All these different resistor values are secret information that Apple doesn't hand out to just anyone. But there are a lot of people who reverse-engineer those values and provide that info for free. However, the special value that causes iPhone 3G/3GS to not alert about an improper device seems to be widely unknown. But I'm telling you that it's simply a 68k Ohm resistor. I've confirmed this on both the 3G and 3GS.
NOTE: This resister value will cause all audio to go through the dock connector. Chargers alone don't require any resistors on the accessory pin to function.
Building your own cable that solves the problem is a major pain. Soldering in such a tiny space is not easy and requires some skill, but it is possible. For more info, like the complete dock connector pinout, please see http://pinouts.ru.
UPDATE: A co-worker had a car charger that caused the "not made to work with iPhone" message to come up. After taking apart the charger and cutting the trace for the accessory pin, the message still came up. This charger, even though it never used the serial commands (such as track forward or back), still connected the serial ground pin to the USB ground pin. After removing that connection (leaving only the USB ground pin connected), the charger worked without any annoying message.
UPDATE 2: I updated my wiring to be based on the Griffin AutoPilot. The idea was not only charge my iPhone and play music through a dedicated AUX-in port, but allow me to have physical buttons play the next/previous song without leaving my current running app. This is accomplished through devices that speak the Apple Serial Accessory Protocol which is really just a (don't quote me) 9600 baud command stream across a couple pins in the dock connector. It has both an advanced and simple mode - in advanced mode the controls on the iPhone/iPod no longer respond and you have to use what you are plugged into to command the device. My wife's car uses the advanced mode and I'm not impressed - the radio sometimes has problems recognizing that it has an iPhone connected despite the iPhone already showing the control lockout message. But, alas, the simple mode seems to bring back the "not made to work with iPhone" message. Not all the time, but about 50% of the time. As soon as I disconnect the serial control wires, the message never appears. I've also seen others reporting the same behavior.