The Binary Paint Shop Problem (BPSP) is an APX-hard optimisation problem arising in automotive manufacturing: given a sequence of 2n cars, comprising n distinct models each appearing twice, the task is to decide which of two colours to paint each car so that the two occurrences of each model are painted differently, while minimising consecutive colour swaps. Performance is measured by the paint swap ratio – the average number of colour changes per car – which directly affects production efficiency and cost. Prior work showed that the Quantum Approximate Optimisation Algorithm (QAOA) at depth p=7 achieves a ratio of 0.393, outperforming the then-best-known classical heuristic, Recursive Greedy, with a proven asymptotic expected ratio of 0.4 [Phys. Rev. A 104, 012403 (2021)]. More recently, the Recursive Star Greedy (RSG) heuristic was proposed with a conjectured expected ratio of 0.361. Here, we formally reduce BPSP to weighted MaxCut, yielding an exact Ising formulation, and benchmark two state-of-the-art low-depth QAOA variants – eXpressive QAOA and Recursive QAOA – at p=1 (denoted XQAOA₁ and RQAOA₁) against four classical BPSP heuristics. Across instances ranging from 2⁷ to 2¹² cars, XQAOA₁ achieves an average paint-swap ratio of 0.357; in our instance-wise benchmarks, it outperforms RQAOA₁ on almost all instances and each of the four classical baselines, including RSG, on every instance. Surprisingly, RQAOA₁ deteriorates with problem size despite employing provably near-optimal QAOA₁ parameters at each recursive step, eventually falling behind RSG at the largest sizes. To our knowledge, this is the first report of size-dependent performance degradation of RQAOA₁ at scale. In contrast, XQAOA₁ remains stable across all tested sizes, with no evidence of size-dependent degradation.