You can just go test it yourself, go run VLC and see how "native" it feels. Its using Qt everywhere except Android.
But if you want to develop cross platform native looking software... Qt is absolutely it. Only option. And it gets better each release. Otherwise you are going the route of the Unity guys, rewriting your program for every single system.
If you want to develop cross platform native looking software, Qt most certainly is not the only option, wxWidgets is. In fact, as you yourself pointed out, Qt isn't really native, just tries to fake the native look and feel. wxWidgets actually is, as it's a thin wrapper around the native toolkits.
This is actually an annoying problem. As a linux user lack of consistency between apps is frustrating but similarly I know people that struggle with changing from mac to windows regularly.
In what way are the native GUIs better? Are they faster/more responsive or do they look better?
Which would be more work over the e.g. 1,2 and 5 year period maintaining three guis or one? (Or is QT not quite cross platform so one ends up maintaining three inferior versions anyway?)