(Disclaimer: This is going entirely off memory and experience. It's very likely that I forgot something in here.)
For the purposes of running a MapleStory private server, you can consider VPS and Dedicated servers to be nearly identical. The only difference is the virtualization layer in the case of VPS: OpenVZ or KVM. There are a few other virtualization platforms out there as well (Xen comes to mind), but I've never had experience with them so I'll refrain from giving an opinion on those.
In either case, as Utsukushi already mentioned, a virtual machine is simply a larger machine that has had its resources split up among multiple users, whereas a dedicated machine is a full machine dedicated entirely to you.
Now, on the different virtualization types:
OpenVZ has the advantage of having (generally) lower prices than KVM for any given set of specs, but be aware that resources in OpenVZ-divided servers are
shared: If somebody else on your machine is abusing their resources, then that will have a negative effect on your server as well, even if your server and theirs have nothing to do with each other. For that reason, it's usually not preferable to run high-demand applications (i.e. game servers) on OpenVZ VPS's, as your performance is not guaranteed.
KVM takes a different approach: When you buy resources on a KVM server, your resources are dedicated entirely to you: that is, only you can use them, and whatever you do will not affect other virtual servers that happen to run on the same machine, or vice-versa. Theoretically, at least. In reality, hard disks tend to be shared between multiple servers even in KVM configurations, with each server simply receiving its own partition. The HDD isn't a bottleneck for MapleStory servers though (unless you did something horribly wrong), so that's not a concern.
A full dedicated server, on the other hand, is literally an entire machine that only you have access to. Other than the network (and often including the network), every resource you have on a dedicated server belongs entirely to you, and it is
impossible for any other server's resource use to affect yours. It doesn't matter if the server machine beside yours is running a dozen servers and overstressing all its resources, your use will be completely unaffected. KVM has this advantage as well, but usually to a lesser degree, as the virtualization layer cannot completely remove interference from other partitions on the same physical machine.
In short: OpenVZ is cheaper but has a shared resource pool, while KVM gives you resources more dedicated to you only. Dedicated machines are "the real deal", so to speak, but usually are more expensive (there are many exceptions to this, though).
That being said, I have to recommend a KVM VPS over a dedicated machine, unless your server reaches 700+ online at once. The reason being that VPS hosting typically has more features available remotely. While dedicated machines usually only have basic functionality from the control panel (power on, power off, reboot, reinstall OS), virtual machines tend to have a much greater array of system administration tools available remotely. Reason being, in a VPS, your server is just, well, virtual; while in a dedicated server, you have an actual physical machine. Unless you really need the (minimal) extra performance and capacity a dedicated server can offer you, go VPS.
And to close, when you're browsing around for server hosts, you would do well to keep in mind the following:
* Hosts that offer VPS hosting but don't tell you what type it is. If it says "burstable RAM" anywhere on the page, it's OpenVZ. Burstable RAM is a feature that belongs entirely to OpenVZ. If it
doesn't have that, then it
might be KVM. Best way to find out is to ask the host directly. Shoot them an e-mail or ticket.
* Whatever hosting company you go to, don't be afraid to ply them with questions (though they probably can't help you do scripting). If they brag about "excellent customer support", take them up on that option. Any hosting company worth its poop will be happy to answer any queries you have, especially ones related to sales and performance.
* Managed hosting: Don't bother. You need root/admin access for most server configurations anyway.
* Always look for reviews before paying anything. There are a
lot of scam companies out there. Remember the saying: If it looks too good to be true, it probably is. An excellent place to look is
You must be registered to see links
. Usually I start with a simple Google search: "site:webhostingtalk.com <name of company> reviews".
* Bandwidth. You don't need a lot of it. 2TB/month is more than plenty. A general rule of thumb is: For every 100 players online, you need 500GB in bandwidth per month. You can work with less, but I find it to be risky. Add more if you need to, bandwidth is usually very flexible.
* Uplink speed. A 100Mbps uplink is about 20 times more than what you need. Fortunately for you, most hosts come with 100Mbps uplinks by default. 1Gbps uplinks are overkill; don't pay for something you don't need.
* If you're running a WZ edited server (and want to host your edits yourself), then different considerations apply: Get more bandwidth. Depending on the size and quantity of your WZ edits, you may want to get anywhere from double to quadruple what I recommended above. Like I said, bandwidth is flexible. Estimate what you need, add some overhead, done.
* Specs: RAM is important, but you shouldn't need more than 8GB. Don't go below 1GB. Anything else, it depends on your server. CPU doesn't really matter for MapleStory servers, get whatever is cheapest. Hard disk: Larger servers need a few hundred GB of disk space for those bulky MySQL databases. Smaller servers, not so much. Most hosts will allow you to upgrade your hard disk if necessary -- get what you need for now, upgrade later. Fortunately, 1TB disks are constantly becoming cheaper. You can probably make do with only 100GB for a small server.
* Lastly, don't be afraid to move hosts! If your current hosting is not working out, or you find a way better deal, then move. At least inform your hosting company of their competition, if nothing else: They're usually glad to know, and the best hosts will offer you a discount or price match.
If that doesn't answer your question, feel free to reply or shoot me a PM.