Are you using Spotify? Skype? VLC? Maybe Quassel? Go checkout some screenshots if not. Take a look. They are all written in Qt.
Who has said that using something like Qt or wxWidgets can't provide a native experience? This is a good comparison of what Qt looks like on different platforms, out-of-the-box. Qt has it's own renderer for most of the themes (some are native), wxWidgets completely uses the different native toolkits.
Spotify is probably one of the best cross platform apps I've seen, hands down.
As far as Skype, they're not even remotely the same app on Mac/Windows.