This is why Google's so far ahead of everyone else in terms of Local Search.
In my experience, you'll have a tough time getting listed in MSN Live Local unless you've purchased a directory listing in the Yellow Pages (SuperPages) phone book. This is what they usually mean by "natural results".
Guide to MSN Local Search
Having contacted Yahoo! myself, I was informed that they do not provide the functionality our neighbours to the South enjoy, which echoes what you were told about them obtaining their listings from natural results.
In addition, Yahoo! Customer Support stated that they're hoping to have Yahoo! Local listings available in Canada "soon". That's it, that's all.
Guide to Yahoo Local Search
There are quite a few more local search providers as well. Some of them might help you, others are still only available in the US.
Other Local Search Marketing Options
Good Luck.