DeviceCapabilities function (Windows)を使えば、各プリンタのトレイ一覧や、インストール済み用紙サイズなどを取得することができます。しかし、プリンタによってはこの関数からの応答にものすごく…数分というオーダーで時間がかかることがあります。
ドライバの内部まで見ていませんが、ドライバ＋同時にインストールするミドルウェアによっては実際にプリンタとの通信を行い、トナー状態や、トレイの情報を取得するようです。したがって、プリンタの電源が入っていなかったり、ネットワークの帯域が小さい場合、時間がかかるのかもしれません。ターミナルサービス上で複数人が同時に使うと混みあうかもしれません。
プリンタドライバで改善されていることもあるようです。まずはドライバの確認、次にプリンタと同時にインストールされる管理ツールを疑ってみましょう。
参考)How To Determine Available PaperBins with DeviceCapabilities API
