i haven't tried it (i just installed), but my guess would be that rc.local will work fine. but be aware that when it gets executed, it's under the root id and the environment may be radically different from that associated with whatever userid you're useing to run it. in particular, you may very well have to specify the full path, or possibly even wrap it in a script that specifies environment variables, etc.
one way to get a hint, depending on the program, of course, is to execute it like this:
/path/to/myprog >/tmp/myprog.log 2>&1
then reboot and go see what /tmp/myprog.log says.
other alternatives are the inittab file and the links in the sysv init runlevel directories, but all of the above applies there equally.
if you've already covered all of that, no offense intended