First of all, AES-256 is considered the gold standard on the market by the industry. The quantum attack on a block cipher is performed by Grover's algorithm that can provide at most quadratic speed up on the key search. The qubit requirements, setup, and running time even for AES-128 is not easily solvable in a near future, and AES-256 is safe. The below table is from
\begin{array}{cccccc}\hline
& \#gates & & depth & & \#qubits\\
k & T & Clifford & T & overall & \\ \hline
128 & 1.19 \cdot 2^{86} & 1.55 \cdot 2^{86} & 1.06 \cdot 2^{80} & 1.16 \cdot 2^{81} & 2953 \\
192 & 1.81 \cdot 2^{118} & 1.17 \cdot 2^{119} & 1.21 \cdot 2^{112} & 1.33 \cdot 2^{113} & 4449 \\
256 & 1.41 \cdot 2^{151} & 1.83 \cdot 2^{151} & 1.44 \cdot 2^{144} & 1.57 \cdot 2^{145} & 6681 \\
\end{array}
Does it increase the security of my data if I split the CBC chunks to let's say 2 clouds? Uploading the even-numbered CBC elements to e.g. Google and the odd-numbered elements to Amazon. Since one storage hoster is constantly missing the next part of the CBC-Chain (1/2 in total) shouldn't this increase security of the data even if the AES key is known by the hoster(s)?
This is a security question on unidentified risks. What if both X and Y are combining their power or they are forced by the government to combine the data, so no benefit there.
What if a huge regression occurs and one of the companies goes out of business so fast. Will you able to get the other chunk? and even in a more catastrophic scenario that your copies are already corrupted.
The hard disks are failing, DVDs degrading, computer systems are not perfect, etc. Solving these is out of Cryptography, the common techniques are multiple copies and raid system like NAS.
Your main issue is the integrity and authentication of your data. To solve this issue you need authenticated encryption and for CBC you can achieve this with HMAC, or better you can use authenticated encryption modes like AES-GCM, Chacha20-Poly1305 those will provide Confidentiality, Integrity, and Authentication. Each has pros and cons mainly take care of the $(IV,key)$ reuse problem.
