There are a number of variables here.
The encryption technology built into Outlook is S/MIME. It uses Public Key Infrastructure certificates just like web-server SSL certs to accomplish what it does. Like HTTPS, the weakness of this system is getting a certificate that everyone can correctly validate. If you don't care about validation, this can be the cheapest solution (free is hard to beat) if you use the Certificate Authority that comes with Active Directory to issue your email certs.
If you require validation to succeed, the above will require anyone you email with to add your AD CA to their Trusted Root store; this is something very few people will actually do. The way around that is to pay one of the Certificate Authority vendors (Thawte, Verisign, etc) for the ability to create Email Certificates that chain to one of their in-everything CA certs. This is a very expensive option if you have to do it for a lot of people. However, if you do so it works just about seamlessly in any email client that supports S/MIME (Thunderbird and Evolution both do, GMail does not).
Also free, but still not supportable on Outlook 2010 is PGP-style certificates based on the GPG package. It is based on the 'web of trust' and has been around for coming close to 20 years now. In order for Outlook to support it, both sides of the email conversation need to have software installed that knows how to handle email signed that way. Gmail doesn't have support for this either.
The non-free option is paying for the actual PGP software suite, which may support Outlook 2010. The problems using it are the same as they are for the GPG based packages, in that both sides of the email conversation need to be able to support email signed that way.
Gmail and Google Apps in general has no support for any kind of email non-repudiation technology. There used to be a Firefox plugin that could do it, but it went unmaintained long enough ago that it is no longer viable. You need an actual email client to support either method. I don't know what iOS supports in this regard either.
S/MIME is built into Outlook and Thunderbird, and even clients who don't have a certificate themselves can validate such emails. This makes S/MIME the obvious choice on which to base your email non-repudiation platform. GPG may be free, but it requires a software install on the client's side to be able to use it.
If you really do want true email non-repudiation you're going to have to pay a lot of money. If you just want the ability to encrypt email, you can get away with free and some end-user hassle.