It turns our that QR codes need to be of a certain size, depending on the length of the URL they are pointing to. Who knew?
An even more detailed analysis can be found here. As usual for posters, the solution is to make it big! (Also, testing the code at final printed size is probably a smart idea.)