The issue with TaxCloud is that it needed to add the FEC checkout pages to the list of pages which TaxCloud loads on. This is done in includes/classes/order.php a core Zen Cart file.
Additionally, the TaxCloud plugin is buggy. When ot_tax is enabled, tax will be duplicated by TaxCloud. If ot_tax is disabled, then no tax will show in the checkout at all (confirmed on default Zen Cart checkout as well as FEC). However, it will magically appear on the invoice when ot_tax is disabled. I am not sure if it is actually getting charged to the customer or just added to the order after the fact as my tests were performed with money order.
Another bug is that TaxCloud was sending the full state name instead of the abbreviations that their API requires. We ended up forking the plugin and have made it freely available here: https://github.com/numinix/TaxCloud. You can see the fix in the commits. This version also includes the customizations to work with Fast and Easy Checkout, Fast and Easy Ajax Checkout, and One Page Responsive Checkout.
The bugs with duplicate tax or tax not showing in the checkout still need to be resolved and we'll be happy to work on those updates if a community member sponsors the work.