"Or it is the problem of VPS, the Web Hosting Company should solve this problem? Or there are bugs in my Perl scripts, I should fix it?"

You mean is the problem with your Perl code which you haven't shown? How are we supposed to know? You haven't even properly described how your code works.

"I do not know how to debug my Perl application. Anyone has similar experience? How to solve this problem?"

"Since it works on a physical Linux box, should I to go with Dedicated Server? Is the dedicated server a physical box? The dedicated server is very expensive in general. I prefer not to choose this solution unless I have no other options."

To solve the problem you need to learn how to debug your Perl code. I suggest starting with Ovid's CGI Course, Web Programming from the tutorials section, basic debugging by logging what your script is doing so you can find out where problems are. You should learn how to debug and benchmark your code, regardless what type of platform it is going to run on. If there are differences between the system you developed (and presentably tested it on) and the system which it runs on, you need to be aware of what impact this will have on your code. You need to be able to prove that the problem isn't with your code before you complain to your VPS host. A dedicated server is a physical server.

Update: s/presentably/presumably/ auto correct fail.