You can use glGetString(GL_EXTENSIONS) to return a string listing all of the extensions supported by the video driver. If the string "GL_NV_texture_rectangle" isn't in the list anywhere, then you can't use GL_TEXTURE_RECTANGLE_NV. Note that this, of course, is only relevant for deprecated GL (pre 3.0) which, judging by the code at the link you are trying to use, I assume is the case.

Also, if rendering using GL_TEXTURE_2D is slow, then you might want to call glGetString(GL_VENDOR). If the vendor string returned is for Microsoft, then your drivers are the software-only drivers installed by default with Windows, and you'll need to install updated drivers from your card manufacturer. This is often the culprit when performance of even simple tasks seems unreasonably slow. This would also possibly result in your desired extension not being supported, since the default Microsoft GL implementation doesn't support many extensions.

GL_TEXTURE_RECTANGLE was originally used for a means of achieving non-power-of-two textures; now most modern hardware supports NPOT textures with GL_TEXTURE_2D.

. . . and most hardware that doesn't, isn't worth your time to write demanding applications for, anyway.

Also remember to be careful of certain state changes, particularly binding. If you're binding a separate texture for each sprite, for instance, you can get substantial slowdowns anywhere, no matter what kind of texture or sampler you're using.