What I would do is first register a domain name with the name of your company. Let's say your company name is "Widgetz". I would register a domain name with the name "widgetz.com". Now, of course, there's probably already a name like that registered, but that's an example.
Once you register your company's name (or a similar name if the name you want is already taken), I would then sign up a "email hosting" provider. Your email would come to
joeblow@widgetz.com, but you'd have another company doing the actual email hosting.
Note: I would also register widgetz.net as well as widgetz.com.
Google "email hosting". Some of these companies will do the registering for you, as well as host your email servers.
Edit: I just googled email hosting, myself. Check out
http://www.registerfly.com/email/ and look at the business section of their offerings. Pretty cheap.