I think it's best to contact some companies for a quote.
I'm sure any company can offer a good deal for the demands you need.
Another option is having a look in the advertising section. Good luck.
» www.InstantDedicated.com - Online in no time » Dedicated Servers in [EU] Netherlands with DAILY support, also on weekends » DDOS Protected network - 100% Money Back if it doesn't work for you » Streaming / IPTV allowed | Up to 10 Gbit ports | 100% Network Uptime
I'd agree, go thru the offers forums, and see if you can find something about the pricerange you want, and then maybe start a live chat on there website, or email their sales/support, and ask to see if they would support a hardware firewall and antispam. As mentioned above, this is not a typical everyday setup, but i'm sure a lot of different providers could accomidate you.