Because power supply efficiency forms a kind of a curve when measured they tend to be more efficient at about 20%-80% load so it's actually recommended to have some extra power draw available, but not too much.
I have an 250-300watts max pc running with a G-550 seasonic which runs at maybe 90% efficiency or more. Hardwaresecrets review loaded it up with 221 watts dc power with 246 watts ac power consumed. http://www.hardwaresecrets.com/article/Seasonic-G-550-Power-Supply-Review/1683/8
If it's going to run at 350 watts at max with synthetic benchmarks and tests or some other extremely stressful application, I would say a 450-550 watts would be more appropriate.
If it's running at 350 watts while running a game or some other somewhat stressful application I would say about 550-700 watts would be ok.
It's true that if your PSU is operating inefficiently because of design or operating circumstances it will actually hurt your system by producing heat and wasting electricity.
Maybe I'm slightly wrong, but usually worrying about too much power is not an issue. Just make sure you don't buy a 900watt unit for a 300 watt pc and make sure it's a reputable power supply brand.