结论：债务公司追债的合法性并非绝对，而是取决于其追债手段是否合法合规，以及是否尊重债务人的合法权益。
详细分析：
债务公司的合法性基础：
- 在我国，并没有专门的法律明确允许“债务公司”这种以追债为业的机构存在。因此，债务公司若要从事追债业务，必须依法成立，具备相关资质和手续，且其经营范围需明确包含相关追债服务（若存在此类合法经营范围）。然而，现实中许多所谓的“债务公司”往往并未获得合法资质，其存在和经营方式本身就存在合法性疑问。
合法追债手段：
- 如果债务公司采取合法、文明、恰当的方式追讨债务，如通过协商、调解或法律途径（如向法院提起诉讼）等，那么这种追债行为是合法的。在此情况下，债权人与债务公司之间应签订明确的委托合同，规定双方的权利、义务及委托权限，确保在法律允许的范围内进行债权清收。
- 举例：债务公司可以协助债权人收集证据，撰写起诉状，并向有管辖权的人民法院提起民事诉讼，通过法律途径解决纠纷。这种方式既合法又有效，能够保护债权人的合法权益。
非法追债手段及后果：
- 部分债务公司可能采用暴力、威胁、恐吓、骚扰、非法拘禁、侵犯隐私等非法手段来追讨债务。这些行为不仅严重侵犯了债务人的合法权益，还可能触犯《治安管理处罚法》甚至《刑法》，构成故意伤害罪、非法拘禁罪、敲诈勒索罪等罪名。
- 举例：如果债务公司对债务人进行频繁的电话骚扰、发送威胁信息，或者非法获取并泄露债务人的个人信息，这些行为都属于违法行为，将受到法律的制裁。
债权人的选择与责任：
- 债权人在选择债务公司时，应充分了解其经营资质、信誉度及追债手段，确保所选债务公司能够遵循法律法规进行合法追债。
- 债权人应与债务公司签订详细的委托合同，明确双方的权利和义务，以及追债过程中的责任承担。这样可以在一定程度上避免债务公司采取非法手段追债，从而保护债权人的自身利益。
建议与警示：
- 谨慎选择债务公司：债权人在选择债务公司时，务必进行充分的调查和了解，确保其具备合法资质和良好信誉。
- 明确委托权限：在签订委托合同时，应详细列明债务公司的权限范围，避免其超越权限行事，导致不必要的法律纠纷。
- 监督追债过程：债权人有权对债务公司的追债过程进行监督，确保其按照合同约定和法律法规进行操作。如果发现债务公司采取非法手段追债，应及时制止并寻求法律帮助。
- 考虑其他合法途径：除了委托债务公司追债外，债权人还可以考虑自行协商、向人民调解委员会申请调解、向法院提起诉讼或申请仲裁等合法途径来追讨债务。
总结：债务公司追债的合法性取决于其追债手段是否合法合规，以及是否尊重债务人的合法权益。债权人在选择债务公司时应谨慎行事，确保委托关系的合法性与安全性。如果遇到债务追讨困难或债务公司采取非法手段追债的情况，建议及时向我咨询，以便获得专业的法律帮助。