Finally, I managed to find out what was causing the problem and resolved it!
I should confess that the problem was not even remotely related to the first 2000 things that comes to mind in these situations! Instead, it was related to the most ridiculous thing that never happened to catch my eye! Well, as they say, it's always in the last place you look!
As weird as it may sound, the problem was related to video scaling! I needed to scale the video and apparently, when you set scaling in vlc, the video wont get fitted to container anymore.
That was it!