Just to update, I got in touch with AppleCare support. For the past week, we went through various configuration options including the suggestions here so far with DNS settings and deletion of preferences files. I highlighted that dictation was working on my iMac but not my MacBook Pro and both computers were connected to the same router and Internet service provider.
I was connected to several senior service advisors who took me through various troubleshooting procedures with no apparent success. In the end, I was asked to download an Apple diagnostic tool which proceeded to collect information from both my MacBook as well as my iMac. I was told that the Apple engineers were keen to find out why dictation works on one Mac but not the other.
I guess that the engineers might have figured out the problem and made adjustments on Apple's servers: I didn't even need to reboot my MacBook Pro at all or delete any preferences files. I didn't even have to switch on or off dictation itself from the system preferences panel. All of a sudden, dictation is now finally working smoothly on my MacBook Pro. I have not had any follow-up calls from AppleCare so far, but whatever the engineers are doing on their side, well done! I will monitor the situation and see whether this dictation continues to work over the next few days.
This message was typed using dictation. For those of you who have been using VPN servers as a solution to the dictation woes do try it now without VPN. I hope that dictation will now work for you without using any VPN servers. Good luck!