Unless they require use of 3CX phones (ie: proprietary linkup ...), they are wrong. If you can (for instance) use Zoiper or X-lite or other soft phones, then Vicidial will work with it as well, but there is a challenge for configuration. It may be a limitation that each phone can only generate one call. If that is the case, you'd have to devise a method to allow Vicidial to link to many phone lines on the 3CX system, instead of using 3CX as a single carrier (so 3CX would become Many Carriers by using all available 3CX agent connections, each with a single line ...). Complex, but doable.
But this sidesteps the basic (underlying) issue. Even with 3CX, there is still a "Carrier". And sending the calls directly to the carrier (not through 3CX) is the desired method of making calls. However, if you have a "package deal" (ie: ripoff), then they require you to use them for the carrier and likely charge you a pretty hefty fee for doing so. Understand that "today's PBX" is FREE (FreePBX, primarily, but also systems like Vicidial which can completely replace your 3CX system!). There is no monthly fee associated with a Free PBX or other PBX like Vicidial unless it is "Hosted" (and then the fee is not for the software, but for the hardware and the internet .... So purchase the hardware (no more monthly fee) and if you can, host it yourself. Now you pay only for internet. If your internet is not sufficient, look for a place to host it for you so you can use their internet. Then the only internet you need at your facility is for ONE call for each agent TO the host location wherever the PBX is located. So instead of 35 calls to support those 5 agents, it will be FIVE calls to support those five agents locally, the rest would be internet at the hosting facility (which always has enough).
You pay per minute for the actual minutes you use, the only "monthly" fees are hosting (if you need it), leasing hardware (if you don't own it) and the "ownership of an inbound number" (aka: DID). That is usually $1-3 per month or $8-10 per month for unlimited inbound (not recommended, though, as they have to limit the number of channels on those unlimited). So you pay $3/month for your DID and per minute for everything else. And in "little" offices like yours that can be a very small number, with no commitment except for the $1-3/month for the DID. IF they are charging you "per user" ... you would do well to find out exactly how many minutes you used during the last billing cycle. Then multiply that by 2 cents. If you come out to less than you were charged for all fees for 3CX service ... you got hosed.