asking about the dedicated server provider

No matter which provider you choose if you don't know your requirements any provider you choose could either be under or over what your business actually requires. Why do you need a dedicated server? Would not provide your own server and just rent rack space in a data center be a better solution?
Would a Virtual Server that you can scale up/down as required be sufficient?
Why can't you setup a workstation as a SMTP server on site?
What are your requirements?

If you intend to run mail service on any server from a rent-a-server provider, plan on (per David's comments above) routing all outgoing mail through a mail relay.  Rent-a-server CIDR blocks are routinely banned en masse by blackhole lists, some of them permanently (Iomart is an example of such.)

Dr. Klahn brings up another good point.

Generally low rent server providers have all their related class C networks blocked.

I see this continually on projects I've called on to fix. And the fix is... you can't use the IP spans provided by this type of hosting.

1) If you use a Mail Relay Service like MailGun then MailGun manages reputation of all their IPs for you.

2) If you use OVH, I've never seen an OVH network blocked.

The reason is OVH has excellent, draconian/harsh spam policies.

Anytime anyone sends spam from an OVH IP, the server these IPs are allocated to is sent a power off signal.

Then the server is put into blocked mode. The only way to move a server out of blocked mode is a full (obliteration of all data) reinstall.

This ensures OVH IPs are clean, so when you lease an IP span... at least so far... I've never seen a single OVH IP on any RBL.

Note: I always am amazed how clean OVH maintains all their IPs.

3) Expanding Dr. Klahn's comment. If you try using low cost hosting companies, the first thing you should do is to test all your IPs to determine if they're RBL'ed.

If they are, you have 2x choices.

a) Request a new IP span from your hosting company, repeatedly, till you get a clean span.

Tip: Never, ever, ever believe any hosting company that tells you their IPs are clean. You must test 100% of all your IPs before you start.

b) Attempt to clean the IP span yourself, which will be costly in time + money.

Tip: Likely best to use MailGun or hire an Email Delivery Consultant to help you design your outgoing MTA infrastructure.