If the maze is not standard but can be anything, the walls can be stored in a quadtree or some similar efficient structure.
Yes. That's why r,theta representation makes more sense computationally because reflection across a normal is just adding and subtracting two angles. Of course, you pay heavily for using only this representation on every tick() during merely linear motion, because in the end our displays are cartesian, and you'll have to convert r,theta to x,y. The solution, of course, is to maintain both representations and use whichever one is faster - a classic space-for-time trade-off.
Modern computers are monstrously fast. So fast that it's hard to imagine just how fast they are. The more time you spend thinking about optimizations before they're necessary, the more time you're not spending on implementing features.
If it's just for fun, though, go for it. A learning exercise is always nice.
To bounce left/right:
To bounce up/down: This representation also generalizes to 3D. You'll have a lot of trouble trying to represent a 3D heading with angles, whereas using a 3D velocity vector is straightforward. (In 3D space, using angles to represent orientation can also suffer from gimbal lock whenever you try to rotate the orientation.)