Why am I unable to delete vertices?
Blender is deleting all the selected vertices, but not all the vertices you want to delete are being selected.

This is because by default blender will not select vertices hidden behind other geometry when using a selection tool like Lasso or Box. To select all geometry including vertices obscured behind other geometry, either perform the selecting in Wireframe view (Z):



Or turn off Limit selection to visible in 3D view > Header to select obscured geometry in solid view: