We have a card processing machine, in house.. However I am looking for a third party PCI compliant encrypted Company to save the credit card information, instead of our backend, for security purposes, and I would just feel more secure having the credit card information separate. Is this a good solution? Is this even possible?
Speak to your current processor, they most definitely have an online solution. You would only need to either hire a developer or if they are popular enough there is probably a 3rd party module available that will integrate with Magento.
We personally do not store any client credit card numbers, only partial and expiry dates.