We examine the prospects of discrete quantum walks (QWs) with trapped ions. In particular, we analyze in detail the limitations of the protocol of Travaglione and Milburn (2002 Phys. Rev. A 65 032310) that has been implemented by several experimental groups in recent years. Based on the first realization in our group (Schmitz et al 2009 Phys. Rev. Lett. 103 090504), we investigate the consequences of leaving the scope of the approximations originally made, such as the Lamb-Dicke approximation. We explain the consequential deviations from the idealized QW for different experimental realizations and an increasing number of steps by taking into account higher-order terms of the quantum evolution. It turns out that these already become significant after a few steps, which is confirmed by experimental results and is currently limiting the scalability of this approach. Finally, we propose a new scheme using short laser pulses, derived from a protocol from the field of quantum computation. We show that this scheme is not subject to the above-mentioned restrictions and analytically and numerically evaluate its limitations, based on a realistic implementation with our specific setup. Implementing the protocol with state-of-the-art techniques should allow for substantially increasing the number of steps to 100 and beyond and should be extendable to higher-dimensional QWs.