For unlubricated friction, the simplistic model is quite good when the surfaces are flat and macroscopic deformation can be neglected. There are three things in particular I would like to elaborate on.
First - the question of the equation of motion that you wrote down. The force of friction, at a microscopic level, is actually a consequence of the breaking of bonds between the surfaces that "stick" together. In other words, you are doing work breaking the bonds, move a small distance, and do it again. If you think of it not as a force, but as work done per unit distance moved, then the conundrum you created goes away. No movement = no work done.
Second - the question of surface deformation. This is actually really important. When you look at the contact area of a ball with a surface, in principle (in the limit of infinite stiffness) the contact happens at a point. In reality, of course, there is some deformation and you end up with a contact area - this would be a circle in the case of a sphere. As the force increases, the "hole" that the sphere makes in the surface becomes deeper (assuming for a moment that the sphere is harder than the surface, for ease of visualization). Now you can see that as the hole becomes deeper, the walls of the hole get steeper - so not only do you have the increase in friction due to the increased normal force (microscopic effect that is valid for flat surfaces) but now you also have to "go uphill" as you try to slide. The net effect is that friction increases faster than linearly with force, once the stresses become large compared to the elastic modulus of the materials involved.
Third - the question of lubrication. Once you add a layer of material between the two objects that slide past each other, viscous forces will add a nonlinear term to the friction - on the one hand, the motion of the surfaces supports the film between the surfaces (which would be squeezed out in the static situation), on the other hand the shear on the film will produce a velocity-dependent term.
The science of friction is complex enough that it has its own name: "tribology". Right there should be a hint that it is indeed not as simple as it sounds... An example (from "Tribology 101" which is a bit more advanced than "high school friction") is the Stribeck curve ("Curva di Stribeck" by A7N8X - Own work. Licensed under Creative Commons Attribution-Share Alike 3.0 via Wikimedia Commons - http://commons.wikimedia.org/wiki/File:Curva_di_Stribeck.svg#mediaviewer/File:Curva_di_Stribeck.svg) - adapted by Floris by adding axis labels with tip of the hat to @ja72:
You can see there are broadly three regimes. At very low velocity, there is no lubrication and you have the "high school" model of constant friction force. In region 2, "mixed friction", the lubrication is starting to have an effect. In region 3, "fluid friction", the lubrication dominates but viscous drag starts to be important.
The exact shape of the curve depends on all kinds of factors - but it shows that your intuition is right, and that there is no simple answer.