Disclaimer: Sonassi is a Magento hosting provider
We have a store with 5,000 skus (and growing, hope to have 10,000 within 3 years)
CE and EE will perform equally with small catalogues like this. In fact, they'll perform about the same until around ~100,000 - when EE will begin to have the edge for catalogue/search pages because of SOLR handoff for layered nav.
Currently in the region of 1m page views and 10,000 orders per month
Working the numbers backwards, based on a 20 day sales period, that equates to around ~500 orders per day.
Assuming 3% conversion, that would equate to around 17,000 unique visitors/day.
Again, this is pretty small numbers for either CE or EE. The busiest CE store we host is around ~250,000 unique visitors/day, so I'd safely safe you've got quite a way to do before you hit any kind of ceiling.
From a purely performance perspective: Magento Community Edition is the same as Enterprise version
You've mentioned caching (Varnish) and something that is extremely important to understand is that caching != performance. No slow store is made faster by using a cache, you merely get the illusion of speed if you load the same page twice - but in the grand scheme of things, caching never improves performance.
One of the key advantages of EE over CE is FPC (a cache), but as caches improve capacity, not speed, this doesn't alter much.
The real speed advantages from EE come from SOLR, beyond that, EE isn't any faster (with the more complex promo rules engine, EE can actually be slower).
I havent seen any difference but the price tag
There's a bigger difference between the two products than just price. Over the years we've seen CE stores move to EE and EE stores move to CE - and they each have their own decisions for it.
However, what I've never seen is anyone migrate to EE because it will improve performance. This should not be a purchasing factor - simply because Magento CE is more than capable of delivering 0.5s (or less) page load times with all the caches off.
We are considering either a server or another server
Turning away from CE/EE as a performance bottleneck - your baseline bottleneck is going to be the hardware and software configuration.
If you've got outdated hardware or a poor software configuration - then its going to severely limit what your potential is going to be. You can only go as fast as your slowest component.
NB. I work for a hosting provider, so take my advice with that bias. But I'd never ever suggest going it alone (eg. OVH/Rackspace etc.) and trying to DIY your hosting. Anyone can set up a server (albeit, not everyone can do it well), but when something goes wrong - and you are losing money, you need an experienced team to rapidly identify and fix your issue.
Put it this way, you wouldn't start your own logistics firm to deliver the goods to your customers (and maintain the vehicles, breakdowns etc.) - don't try and do the same thing with your hosting (the most important facet of your online business).
There's a world of difference between "Magento optimised" hosting from your typical managed providers and companies like ourselves - that have wholly specialised in Magento hosting since its inception.